Random

Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph $ G $, we define $ \Delta(G) $ to be the maximum degree, $ \omega(G) $ to be the size of the largest clique subgraph, and $ \chi(G) $ to be the chromatic number of $ G $.

Conjecture   $ \chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)} $ for every graph $ G $.

Keywords: coloring

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every $ 4 $-connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

Extremal problem on the number of tree endomorphism ★★

Author(s): Zhicong Lin

Conjecture   An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the $ n $ vertices' trees, the star with $ n $ vertices has the most endomorphisms, while the path with $ n $ vertices has the least endomorphisms.

Keywords:

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:

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant $ c $ such that the list chromatic number of any bipartite graph $ G $ of maximum degree $ \Delta $ is at most $ c \log \Delta $.

Keywords:

Beneš Conjecture ★★★

Author(s): Beneš

Given a partition $ \bf h $ of a finite set $ E $, stabilizer of $ \bf h $, denoted $ S(\bf h) $, is the group formed by all permutations of $ E $ preserving each block in $ \mathbf h $.

Problem  ($ \star $)   Find a sufficient condition for a sequence of partitions $ {\bf h}_1, \dots, {\bf h}_\ell $ of $ E $ to be universal, i.e. to yield the following decomposition of the symmetric group $ \frak S(E) $ on $ E $: $$ (1)\quad \frak S(E) = S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell).  $$ In particular, what about the sequence $ \bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h) $, where $ \delta $ is a permutation of $ E $?
Conjecture  (Beneš)   Let $ \bf u $ be a uniform partition of $ E $ and $ \varphi $ be a permutation of $ E $ such that $ \bf u\wedge\varphi(\bf u)=\bf 0 $. Suppose that the set $ \big(\varphi S({\bf u})\big)^{n} $ is transitive, for some integer $ n\ge2 $. Then $$ \frak S(E) = \big(\varphi S({\bf u})\big)^{2n-1}. $$

Keywords:

Discrete Logarithm Problem ★★★

Author(s):

If $ p $ is prime and $ g,h \in {\mathbb Z}_p^* $, we write $ \log_g(h) = n $ if $ n \in {\mathbb Z} $ satisfies $ g^n =  h $. The problem of finding such an integer $ n $ for a given $ g,h \in {\mathbb Z}^*_p $ (with $ g \neq 1 $) is the Discrete Log Problem.

Conjecture   There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

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

Singmaster's conjecture ★★

Author(s): Singmaster

Conjecture   There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number $ 1 $.

The number $ 2 $ appears once in Pascal's triangle, $ 3 $ appears twice, $ 6 $ appears three times, and $ 10 $ appears $ 4 $ times. There are infinite families of numbers known to appear $ 6 $ times. The only number known to appear $ 8 $ times is $ 3003 $. It is not known whether any number appears more than $ 8 $ times. The conjectured upper bound could be $ 8 $; Singmaster thought it might be $ 10 $ or $ 12 $. See Singmaster's conjecture.

Keywords: Pascal's triangle

Rota's unimodal conjecture ★★★

Author(s): Rota

Let $ M $ be a matroid of rank $ r $, and for $ 0 \le i \le r $ let $ w_i $ be the number of closed sets of rank $ i $.

Conjecture   $ w_0,w_1,\ldots,w_r $ is unimodal.
Conjecture   $ w_0,w_1,\ldots,w_r $ is log-concave.

Keywords: flat; log-concave; matroid

Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

Problem   Bound the extremal number of $ C_{10} $ in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture   If $ M_1,\ldots,M_k $ are matroids on $ E $ and $ \sum_{i=1}^k rk_{M_i}(X_i) \ge \ell (k-1) $ for every partition $ \{X_1,\ldots,X_k\} $ of $ E $, then there exists $ X \subseteq E $ with $ |X| = \ell $ which is independent in every $ M_i $.

Keywords: independent set; matroid; partition

4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let $ B \subseteq {\mathbb N} $. The representation function $ r_B : {\mathbb N} \rightarrow {\mathbb N} $ for $ B $ is given by the rule $ r_B(k) = \#\{ (i,j) \in B \times B : i + j = k \} $. We call $ B $ an additive basis if $ r_B $ is never $ 0 $.

Conjecture   If $ B $ is an additive basis, then $ r_B $ is unbounded.

Keywords: additive basis; representation function

Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

Conjecture   Let $ D $ be a digraph all of whose strong components are nontrivial. Then $ D $ contains a cyclic spanning subdigraph with cyclomatic number at most $ \alpha(D) $.

Keywords:

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

Keywords: list assignment; list coloring

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

Realisation problem for the space of knots in the 3-sphere ★★

Author(s): Budney

Problem   Given a link $ L $ in $ S^3 $, let the symmetry group of $ L $ be denoted $ Sym(L) = \pi_0 Diff(S^3,L) $ ie: isotopy classes of diffeomorphisms of $ S^3 $ which preserve $ L $, where the isotopies are also required to preserve $ L $.

Now let $ L $ be a hyperbolic link. Assume $ L $ has the further `Brunnian' property that there exists a component $ L_0 $ of $ L $ such that $ L \setminus L_0 $ is the unlink. Let $ A_L $ be the subgroup of $ Sym(L) $ consisting of diffeomorphisms of $ S^3 $ which preserve $ L_0 $ together with its orientation, and which preserve the orientation of $ S^3 $.

There is a representation $ A_L \to \pi_0 Diff(L \setminus L_0) $ given by restricting the diffeomorphism to the $ L \setminus L_0 $. It's known that $ A_L $ is always a cyclic group. And $ \pi_0 Diff(L \setminus L_0) $ is a signed symmetric group -- the wreath product of a symmetric group with $ \mathbb Z_2 $.

Problem: What representations can be obtained?

Keywords: knot space; symmetry

4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem   Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

P vs. PSPACE ★★★

Author(s): Folklore

Problem   Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

Chords of longest cycles ★★★

Author(s): Thomassen

Conjecture   If $ G $ is a 3-connected graph, every longest cycle in $ G $ has a chord.

Keywords: chord; connectivity; cycle

Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with $ k $ edges. Define a form parameter for a polyhedron as $ \beta:= v/(k+2) $ where $ v $ is the number of vertices. What is the distribution of $ \beta $ for $ k \to \infty $?

Keywords: polyhedral graphs, distribution

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family $ {\mathcal F} $ of graphs is $ \chi $-bounded if there exists a function $ f: {\mathbb N} \rightarrow {\mathbb N} $ so that every $ G \in {\mathcal F} $ satisfies $ \chi(G) \le f (\omega(G)) $.

Conjecture   For every fixed tree $ T $, the family of graphs with no induced subgraph isomorphic to $ T $ is $ \chi $-bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-polytope $ P $ is defined to be $ (f_1 + f_2)/(f_0 + f_3) $ where $ f_i $ is the number of faces of $ P $ of dimension $ i $.

Question   Does there exist a fixed constant $ c $ so that every convex 4-polytope has fatness at most $ c $?

Keywords: f-vector; polytope

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

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let $ r $ be a positive integer. We say that a graph $ G $ is strongly $ r $-colorable if for every partition of the vertices to sets of size at most $ r $ there is a proper $ r $-coloring of $ G $ in which the vertices in each set of the partition have distinct colors.

Conjecture   If $ \Delta $ is the maximal degree of a graph $ G $, then $ G $ is strongly $ 2 \Delta $-colorable.

Keywords: strong coloring

Monochromatic empty triangles ★★★

Author(s):

If $ X \subseteq {\mathbb R}^2 $ is a finite set of points which is 2-colored, an empty triangle is a set $ T \subseteq X $ with $ |T|=3 $ so that the convex hull of $ T $ is disjoint from $ X \setminus T $. We say that $ T $ is monochromatic if all points in $ T $ are the same color.

Conjecture   There exists a fixed constant $ c $ with the following property. If $ X \subseteq {\mathbb R}^2 $ is a set of $ n $ points in general position which is 2-colored, then it has $ \ge cn^2 $ monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

Packing T-joins ★★

Author(s): DeVos

Conjecture   There exists a fixed constant $ c $ (probably $ c=1 $ suffices) so that every graft with minimum $ T $-cut size at least $ k $ contains a $ T $-join packing of size at least $ (2/3)k-c $.

Keywords: packing; T-join

Criterion for boundedness of power series

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence $ (a_n) $ so that the power series $ \sum_{n=0}^{\infty} a_n x^n $ is bounded for all $ x \in \mathbb{R} $.

Keywords: boundedness; power series; real analysis

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; line graphs

Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture   Every simple graph with maximum degree $ \Delta $ has a proper $ (\Delta+2) $-edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times  n $ grid. The first player (if any) to occupy a set of $ n $ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph $ H $, there exists a constant $ \delta(H) $, so that every graph $ G $ without an induced subgraph isomorphic to $ H $ contains either a clique or an independent set of size $ |V(G)|^{\delta(H)} $.

Keywords: induced subgraph

trace inequality ★★

Author(s):

Let $ A,B $ be positive semidefinite, by Jensen's inequality, it is easy to see $ [tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}} $, whenever $ s>r>0 $.

What about the $ tr(A^s+B^s)^{\frac{1}{s}}\leq tr(A^r+B^r)^{\frac{1}{r}} $, is it still valid?

Keywords:

The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of $ \mathbb{R}^n $ containing no pair of orthogonal vectors is attained by two open caps of geodesic radius $ \pi/4 $ around the north and south poles.

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let $ r \ge 2 $ be an integer and let $ H $ be a minor minimal clutter with $ \frac{1}{r}\tau_r(H) < \tau(H) $. Then either $ H $ has a $ J_k $ minor for some $ k \ge 2 $ or $ H $ has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

Burnside problem ★★★★

Author(s): Burnside

Conjecture   If a group has $ r $ generators and exponent $ n $, is it necessarily finite?

Keywords:

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a $ k $-outerplanar embedding for which $ k $ is minimal can be found in polynomial time. Does a similar result hold for $ k $-edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

Conjecture   If $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

Keywords:

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform hypergraph, and assume that every set of $ d-1 $ points is contained in at most $ r $ edges. Then there exists an $ r+d-1 $-edge-coloring so that any two edges which share $ d-1 $ vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

Cycle Double Covers Containing Predefined 2-Regular Subgraphs ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ G $ be a $ 2 $-connected cubic graph and let $ S $ be a $ 2 $-regular subgraph such that $ G-E(S) $ is connected. Then $ G $ has a cycle double cover which contains $ S $ (i.e all cycles of $ S $).

Keywords:

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let $ G $ be the disjoint union of the graphs $ G_1 $ and $ G_2 $ and let $ \Sigma $ be a surface. Is it true that every optimal drawing of $ G $ on $ \Sigma $ has the property that $ G_1 $ and $ G_2 $ are disjoint?

Keywords: crossing number; surface

Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set $ S \subseteq {\mathbb R}^2 $ so that all pairwise distances between points in $ S $ are rational?

Keywords: integral distance; rational distance

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

Obstacle number of planar graphs

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some $ k $ such that every planar graph has obstacle number at most $ k $?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture   Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

Convex uniform 5-polytopes ★★

Author(s):

Problem   Enumerate all convex uniform 5-polytopes.

Keywords:

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $ G $ be an (additive) abelian group, and for every $ S \subseteq G $ let $ {\mathit stab}(S) = \{ g \in G : g + S = S \} $.

Conjecture   Let $ M $ be a matroid on $ E $, let $ w : E \rightarrow G $ be a map, put $ S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \} $ and $ H = {\mathit stab}(S) $. Then $$|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$$

Keywords: matroid; sumset; zero sum