Recent Activity

Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

Conjecture   For every graph $ G $,
(a) $ \chi_f(G)\leq\text{had}(G) $
(b) $ \chi(G)\leq\text{had}_f(G) $
(c) $ \chi_f(G)\leq\text{had}_f(G) $.

Keywords: fractional coloring, minors

Generalized path-connectedness in proximity spaces ★★

Author(s): Porton

Let $ \delta $ be a proximity.

A set $ A $ is connected regarding $ \delta $ iff $ \forall X,Y \in \mathscr{P} A \setminus \{ \emptyset \} : \left( X \cup Y = A \Rightarrow X \mathrel{\delta} Y \right) $.

Conjecture   The following statements are equivalent for every endofuncoid $ \mu $ and a set $ U $:
    \item $ U $ is connected regarding $ \mu $. \item For every $ a, b \in U $ there exists a totally ordered set $ P \subseteq   U $ such that $ \min P = a $, $ \max P = b $, and for every partion $ \{ X, Y \} $ of $ P $ into two sets $ X $, $ Y $ such that $ \forall x \in X, y \in Y : x < y $, we have $ X \mathrel{[ \mu]^{\ast}} Y $.

Keywords: connected; connectedness; proximity space

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
    \item $ ( \mathsf{\tmop{FCD}}) g = f $; \item $ 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

Point sets with no empty pentagon

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

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

Separators in string graphs ★★

Author(s): Fox; Pach; Tóth

Conjecture   Every string graph with $ m $ edges has a separator of size $ O(\sqrt{m}) $.

Keywords: separator; string graphs

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 $,
    \item If $ n=2k $, then $ |RC(n)|=4 $. \item If $ n=2k+1 $, then $ |RC(n)|=2^j $ with $ j\leq k+1 $.
Conjecture  (Odd Sum conjecture)   Given $ \pi\in RC(n) $,
    \item If $ n=2k+1 $, then $ \pi_j+\pi_{n-j+1} $ is odd for $ 1\leq j\leq k $. \item If $ n=2k $, then $ \pi_j + \pi_{n-j+1} = 2k+1 $ for all $ 1\leq j\leq k $.

Keywords:

Rota's basis conjecture ★★★

Author(s): Rota

Conjecture   Let $ V $ be a vector space of dimension $ n $ and let $ B_1,\ldots,B_n \subseteq V $ be bases. Then there exist $ n $ disjoint transversals of $ B_1,\ldots,B_n $ each of which is a base.

Keywords: base; latin square; linear algebra; matroid; transversal

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:

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

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued reloid is monovalued.

Keywords:

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

Decomposition of completions of reloids ★★

Author(s): Porton

Conjecture   For composable reloids $ f $ and $ g $ it holds
    \item $ \operatorname{Compl} ( g \circ f) = ( \operatorname{Compl} g) \circ f $ if $ f $ is a co-complete reloid; \item $ \operatorname{CoCompl} ( f \circ g) = f \circ \operatorname{CoCompl} g $ if $ f $ is a complete reloid; \item $ \operatorname{CoCompl} ( ( \operatorname{Compl} g) \circ f) = \operatorname{Compl} ( g \circ   ( \operatorname{CoCompl} f)) = ( \operatorname{Compl} g) \circ ( \operatorname{CoCompl} f) $; \item $ \operatorname{Compl} ( g \circ ( \operatorname{Compl} f)) = \operatorname{Compl} ( g \circ   f) $; \item $ \operatorname{CoCompl} ( ( \operatorname{CoCompl} g) \circ f) = \operatorname{CoCompl} ( g   \circ f) $.

Keywords: co-completion; completion; reloid

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

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

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

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

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

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

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: