Random

Lovász Path Removal Conjecture ★★

Author(s): Lovasz

Conjecture   There is an integer-valued function $ f(k) $ such that if $ G $ is any $ f(k) $-connected graph and $ x $ and $ y $ are any two vertices of $ G $, then there exists an induced path $ P $ with ends $ x $ and $ y $ such that $ G-V(P) $ is $ k $-connected.

Keywords:

Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem   Is it true for all $ n \ge 0 $, that every sufficiently large $ n $-connected graph without a $ K_n $ minor has a set of $ n-5 $ vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If $ A $ is 2-large, then $ A $ is large.

Keywords: 2-large sets; large sets

Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture   For every $ k\geq 2 $, there is an integer $ f(k) $ so that every strongly $ f(k) $-connected tournament has $ k $ edge-disjoint Hamilton cycles.

Keywords:

Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer $ n \geq 1 $, it is impossible to cover a square of side greater than $ n $ with $ n^2+1 $ unit squares.

Keywords:

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

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

Square achievement game on an n x n 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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

The $ d $-dimensional (hyper)cube $ Q_d $ is the graph whose vertices are all binary sequences of length $ d $, and two of the sequences are adjacent in $ Q_d $ if they differ in precisely one coordinate.

Conjecture   $ \displaystyle \lim  \frac{cr(Q_d)}{4^d} = \frac{5}{32} $

Keywords: crossing number; hypercube

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let $ G $ be a perfect graph on $ n $ vertices. Is it true that either $ G $ or $ \bar{G} $ contains a complete bipartite subgraph with bipartition $ (A,B) $ so that $ |A|, |B| \ge n^{1 - o(1)} $?

Keywords: perfect graph

Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of $ \mathbb Q $.

Keywords:

Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope

Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph $ G $ is the multiset consisting of all unlabelled subgraphs obtained from $ G $ by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on $ \ge 3 $ vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

Concavity of van der Waerden numbers ★★

Author(s): Landman

For $ k $ and $ \ell $ positive integers, the (mixed) van der Waerden number $ w(k,\ell) $ is the least positive integer $ n $ such that every (red-blue)-coloring of $ [1,n] $ admits either a $ k $-term red arithmetic progression or an $ \ell $-term blue arithmetic progression.

Conjecture   For all $ k $ and $ \ell $ with $ k \geq \ell $, $ w(k,\ell) \geq w(k+1,\ell-1) $.

Keywords: arithmetic progression; van der Waerden

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:

Matching cut and girth ★★

Author(s):

Question   For every $ d $ does there exists a $ g $ such that every graph with average degree smaller than $ d $ and girth at least $ g $ has a matching-cut?

Keywords: matching cut, matching, cut

Are there infinite number of Mersenne Primes? ★★★★

Author(s):

Conjecture   A Mersenne prime is a Mersenne number \[ M_n  = 2^p  - 1 \] that is prime.

Are there infinite number of Mersenne Primes?

Keywords: Mersenne number; Mersenne prime

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let $ a > b > 0 $ be integers. Set $ b_1 = b $ and $ b_{i+1} = {a \bmod {b_i}} $ for $ i \geq 0 $. Eventually we have $ b_{n+1} = 0 $; put $ P(a,b) = n $.

Example: $ P(35, 22) = 7 $, since $ b_1 = 22 $, $ b_2 = 13 $, $ b_3 = 9 $, $ b_4 = 8 $, $ b_5 = 3 $, $ b_6 = 2 $, $ b_7 = 1 $, $ b_8 = 0 $.

Prove or disprove: $ P(a,b) = O((\log a)^2) $.

Keywords: Pierce expansions

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture   Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

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

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

Covering powers of cycles with equivalence subgraphs

Author(s):

Conjecture   Given $ k $ and $ n $, the graph $ C_{n}^k $ has equivalence covering number $ \Omega(k) $.

Keywords:

The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let $ f(n) = 3n+1 $ if $ n $ is odd and $ \frac{n}{2} $ if $ n $ is even. Let $ f(1) = 1 $. Assume we start with some number $ n $ and repeatedly take the $ f $ of the current number. Prove that no matter what the initial number is we eventually reach $ 1 $.

Keywords: integer sequence

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

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation $ G $ has a dominating set of size $ \le \frac{1}{4} |V(G)| $.

Keywords: coloring; domination; multigrid; planar graph; triangulation

Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer $ k $, there exists an integer $ d $ so that every polytope of dimension $ \ge d $ has a $ k $-dimensional face which is either a simplex or is combinatorially isomorphic to a $ k $-dimensional cube.

Keywords: cube; facet; polytope; simplex

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $ S $ be a set of points in the plane. Two points $ v $ and $ w $ in $ S $ are visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

Conjecture   For all integers $ k,\ell\geq2 $ there is an integer $ n $ such that every set of at least $ n $ points in the plane contains at least $ \ell $ collinear points or $ k $ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let $ M,M' $ be abelian groups and let $ B \subseteq M $ and $ B' \subseteq M' $ satisfy $ B=-B $ and $ B' = -B' $. If there is a homomorphism from $ Cayley(M,B) $ to $ Cayley(M',B') $, then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

Exact colorings of graphs ★★

Author(s): Erickson

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: graph coloring; ramsey theory

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

3-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let $ X $ be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of $ X $.

Keywords: Hodge Theory; Millenium Problems

Lindelöf hypothesis ★★

Author(s): Lindelöf

Conjecture   For any $ \epsilon>0 $ $$\zeta\left(\frac12 + it\right) \mbox{ is }\mathcal{O}(t^\epsilon).$$

Since $ \epsilon $ can be replaced by a smaller value, we can also write the conjecture as, for any positive $ \epsilon $, $$\zeta\left(\frac12 + it\right) \mbox{ is }o(t^\varepsilon).$$

Keywords: Riemann Hypothesis; zeta

Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

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:

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An alternating walk in a digraph is a walk $ v_0,e_1,v_1,\ldots,v_m $ so that the vertex $ v_i $ is either the head of both $ e_i $ and $ e_{i+1} $ or the tail of both $ e_i $ and $ e_{i+1} $ for every $ 1 \le i \le m-1 $. A digraph is universal if for every pair of edges $ e,f $, there is an alternating walk containing both $ e $ and $ f $

Question   Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture   For every prime $ p $, there is a constant $ c(p) $ (possibly $ c(p)=p $) so that the union (as multisets) of any $ c(p) $ bases of the vector space $ ({\mathbb Z}_p)^n $ contains an additive basis.

Keywords: additive basis; matrix

Another conjecture about reloids and funcoids ★★

Author(s): Porton

Definition   $ \square f = \bigcap^{\mathsf{RLD}} \mathrm{up}^{\Gamma (\operatorname{Src} f ; \operatorname{Dst} f)} f $ for reloid $ f $.
Conjecture   $ (\mathsf{RLD})_{\Gamma} f = \square (\mathsf{RLD})_{\mathrm{in}} f $ for every funcoid $ f $.

Note: it is known that $ (\mathsf{RLD})_{\Gamma} f \ne \square (\mathsf{RLD})_{\mathrm{out}} f $ (see below mentioned online article).

Keywords:

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $ G $ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index $ s\chi'(G) $ is the minimum number of colours in a strong edge-colouring of $ G $.

Conjecture   $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$

Keywords:

Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph $ G $ satisfy $ \gamma(G) \le \lceil |G|/3 \rceil $ ?

Keywords: cubic graph; domination

Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

Conjecture   Every graph with minimum degree at least 7 contains a $ K_6 $-minor.
Conjecture   Every 7-connected graph contains a $ K_6 $-minor.

Keywords: connectivity; graph minors

Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family $ {\cal F} $ of graphs and an integer $ n $, the Turán number $ ex(n,{\cal F}) $ of $ {\cal F} $ is the largest integer $ m $ such that there exists a graph on $ n $ vertices with $ m $ edges which contains no member of $ {\cal F} $ as a subgraph.

Conjecture   For every finite family $ {\cal F} $ of graphs there exists an $ F\in {\cal F} $ such that $ ex(n, F ) = O(ex(n, {\cal F})) $ .

Keywords:

Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

The permanent conjecture ★★

Author(s): Kahn

Conjecture   If $ A $ is an invertible $ n \times n $ matrix, then there is an $ n \times n $ submatrix $ B $ of $ [A A] $ so that $ perm(B) $ is nonzero.

Keywords: invertible; matrix; permanent

Are there an infinite number of lucky primes?

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

Lucas Numbers Modulo m ★★

Author(s):

Conjecture   The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1.

Keywords: Lucas numbers

Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem   Is it true that for every $ r $, all but finitely many $ r $-regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $ G $ is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   $ K_n $ is the only $ n $-chromatic double-critical graph

Keywords: coloring; complete graph