Recent Activity

Direct proof of a theorem about compact funcoids ★★

Author(s): Porton

Conjecture Let $f$ is a $T_1$ -separable (the same as $T_2$ for symmetric transitive) compact funcoid and $g$ is a uniform space (reflexive, symmetric, and transitive endoreloid) such that $( \mathsf{\tmop{FCD}}) g = f$ . Then $g = \langle f \times f \rangle^{\ast} \Delta$ .

The main purpose here is to find a direct proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.

The direct proof may be constructed by correcting all errors an omissions in this draft article.

Direct proof could be better because with it we would get a little more general statement like this:

Conjecture Let $f$ be a $T_1$ -separable compact reflexive symmetric funcoid and $g$ be a reloid such that

$( \mathsf{\tmop{FCD}}) g = f$

$g \circ g^{- 1} \sqsubseteq g$

Then $g = \langle f \times f \rangle^{\ast} \Delta$ .

Keywords: compact space; compact topology; funcoid; reloid; uniform space; uniformity

Posted by porton
updated February 8th, 2014

add new comment

Dirac's Conjecture ★★

Author(s): Dirac

Conjecture For every set $P$ of $n$ points in the plane, not all collinear, there is a point in $P$ contained in at least $\frac{n}{2}-c$ lines determined by $P$ , for some constant $c$ .

Keywords: point set

Posted by David Wood
updated January 22nd, 2014

add new comment

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $S_n$ denote the set of all permutations of $[n]=\set{1,2,\ldots,n}$ . Let $i(\pi)$ and $d(\pi)$ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $\pi$ . Let $X(\pi)$ denote the set of subsequences of $\pi$ with length at least three. Let $t(\pi)$ denote $\sum_{\tau\in X(\pi)}(i(\tau)+d(\tau))$ .

A permutation $\pi\in S_n$ is called a Roller Coaster permutation if $t(\pi)=\max_{\tau\in S_n}t(\tau)$ . Let $RC(n)$ be the set of all Roller Coaster permutations in $S_n$ .

Conjecture For $n\geq 3$ ,

$n=2k$

$|RC(n)|=4$

$n=2k+1$

$|RC(n)|=2^j$

$j\leq k+1$

Conjecture (Odd Sum conjecture) Given $\pi\in RC(n)$ ,

$n=2k+1$

$\pi_j+\pi_{n-j+1}$

$1\leq j\leq k$

$n=2k$

$\pi_j + \pi_{n-j+1} = 2k+1$

$1\leq j\leq k$

Keywords:

Posted by Tanbir Ahmed
updated October 14th, 2013

add new comment

Graphs of exact colorings ★★

Author(s):

Conjecture For $c \geq m \geq 1$ , let $P(c,m)$ be the statement that given any exact $c$ -coloring of the edges of a complete countably infinite graph (that is, a coloring with $c$ colors all of which must be used at least once), there exists an exactly $m$ -colored countably infinite complete subgraph. Then $P(c,m)$ is true if and only if $m=1$ , $m=2$ , or $c=m$ .

Keywords:

Posted by sabisood
updated October 3rd, 2013

add new comment

Imbalance conjecture ★★

Author(s): Kozerenko

Conjecture Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$ . Then $M_{G}$ is graphic.

Keywords: edge imbalance; graphic sequences

Posted by Sergiy Kozerenko
updated September 24th, 2013

add new comment

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

Conjecture Every metamonovalued reloid is monovalued.

Keywords:

Posted by porton
updated September 17th, 2013

add new comment

Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

Conjecture Every metamonovalued funcoid is monovalued.

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

Posted by porton
updated September 17th, 2013

add new comment

Decomposition of completions of reloids ★★

Author(s): Porton

Conjecture For composable reloids $f$ and $g$ it holds

$\operatorname{Compl} ( g \circ f) = ( \operatorname{Compl} g) \circ f$

$f$

$\operatorname{CoCompl} ( f \circ g) = f \circ \operatorname{CoCompl} g$

$f$

$\operatorname{CoCompl} ( ( \operatorname{Compl} g) \circ f) = \operatorname{Compl} ( g \circ ( \operatorname{CoCompl} f)) = ( \operatorname{Compl} g) \circ ( \operatorname{CoCompl} f)$

$\operatorname{Compl} ( g \circ ( \operatorname{Compl} f)) = \operatorname{Compl} ( g \circ f)$

$\operatorname{CoCompl} ( ( \operatorname{CoCompl} g) \circ f) = \operatorname{CoCompl} ( g \circ f)$

Keywords: co-completion; completion; reloid

Posted by porton
updated September 2nd, 2013

add new comment

Graph Theory » Coloring

List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$ .

Keywords: list coloring; Total coloring; total graphs

Posted by Jon Noel
updated August 29th, 2013

add new comment

Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by projective plane we mean the set of all lines through the origin in $\mathbb{R}^3$ .

Definition Say that a subset $S$ of the projective plane is octahedral if all lines in $S$ pass through the closure of two opposite faces of a regular octahedron centered at the origin.

Definition Say that a subset $S$ of the projective plane is weakly octahedral if every set $S'\subseteq S$ such that $|S'|=3$ is octahedral.

Conjecture Suppose that the projective plane can be partitioned into four sets, say $S_1,S_2,S_3$ and $S_4$ such that each set $S_i$ is weakly octahedral. Then each $S_i$ is octahedral.

Keywords: Partitioning; projective plane

Posted by Jon Noel
updated August 27th, 2013

add new comment

Graph Theory » Basic G.T. » Connectivity

Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$ . Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$ .

Keywords: Disjoint paths; edge-connectivity; spanning trees

Posted by Jon Noel
updated August 25th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture If $G$ is a non-empty graph containing no induced odd cycle of length at least $5$ , then there is a $2$ -vertex colouring of $G$ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

Posted by Jon Noel
updated August 25th, 2013

add new comment

Graph Theory » Basic G.T.

Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

Conjecture Denote by $NH(n)$ the number of non-Hamiltonian 3-regular graphs of size $2n$ , and similarly denote by $NHB(n)$ the number of non-Hamiltonian 3-regular 1-connected graphs of size $2n$ .

Is it true that $\lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1$ ?

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Posted by mhaythorpe
updated August 23rd, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture If $G$ is a simple graph which is the union of $k$ pairwise edge-disjoint complete graphs, each of which has $k$ vertices, then the chromatic number of $G$ is $k$ .

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013

add new comment

Number Theory » Analytic N.T.

Are there only finite Fermat Primes? ★★★

Author(s):

Conjecture A Fermat prime is a Fermat number $F_n = 2^{2^n } + 1$ that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

Posted by kurtulmehtap
updated August 21st, 2013

add new comment

Number Theory » Analytic N.T.

Are all Fermat Numbers square-free? ★★★

Author(s):

Conjecture Are all Fermat Numbers $F_n = 2^{2^{n } } + 1$ Square-Free?

Keywords:

Posted by kurtulmehtap
updated August 21st, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question (Noel, 2013) Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$ , $\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?$

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013

add new comment

Graph Theory » Directed Graphs

Erdős-Posa property for long directed cycles ★★

Author(s): Havet; Maia

Conjecture Let $\ell \geq 2$ be an integer. For every integer $n\geq 0$ , there exists an integer $t_n=t_n(\ell)$ such that for every digraph $D$ , either $D$ has a $n$ pairwise-disjoint directed cycles of length at least $\ell$ , or there exists a set $T$ of at most $t_n$ vertices such that $D-T$ has no directed cycles of length at least $\ell$ .

Keywords:

Posted by fhavet
updated June 25th, 2013

add new comment

Graph Theory » Directed Graphs

Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

Conjecture Every planar oriented graph $D$ has an acyclic induced subdigraph of order at least $\frac{3}{5} |V(D)|$ .

Keywords:

Posted by fhavet
updated June 25th, 2013

add new comment

Polignac's Conjecture ★★★

Author(s): de Polignac

Conjecture Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.

In particular, this implies:

Conjecture Twin Prime Conjecture: There are an infinite number of twin primes.

Keywords: prime; prime gap

Posted by Hugh Barker
updated June 18th, 2013