Random

Unit vector flows ★★

Author(s): Jain

\begin{conjecture} For every graph $G$ without a \Def[bridge]{bridge (graph theory)}, there is a flow $\phi : E(G) \rightarrow S^2 = \{ x \in {\mathbb R}^3 : |x| = 1 \}$.

\end{conjecture}

\begin{conjecture} There exists a map $q:S^2 \rightarrow \{-4,-3,-2,-1,1,2,3,4\}$ so that antipodal points of $S^2$ receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero. \end{conjecture}

Keywords: nowhere-zero flow

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

\begin{conjecture} Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle. \end{conjecture}

Keywords:

Lucas Numbers Modulo m ★★

Author(s):

\begin{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. \end{conjecture}

Keywords: Lucas numbers

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

\begin{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$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Ramsey properties of Cayley graphs ★★★

Author(s): Alon

\begin{conjecture} There exists a fixed constant $c$ so that every abelian group $G$ has a subset $S \subseteq G$ with $-S = S$ so that the \Def[Cayley graph]{cayley graph} ${\mathit Cayley}(G,S)$ has no clique or independent set of size $> c \log |G|$. \end{conjecture}

Keywords: Cayley graph; Ramsey number

Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

\begin{conjecture} The order of the largest total curvature of the primal central path over all polytopes defined by $n$ inequalities in dimension $d$ is $n$. \end{conjecture}

Keywords: curvature; polytope

Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

\begin{conjecture} Every bidirected graph with a nowhere-zero $k$-flow for some $k$, has a nowhere-zero $6$-flow. \end{conjecture}

Keywords: bidirected graph; nowhere-zero flow

Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

\begin{conjecture} Every 4-connected \Def{line graph} is \Def[hamiltonian]{Hamilton cycle}. \end{conjecture}

Keywords: hamiltonian; line graphs

The Hodge Conjecture ★★★★

Author(s): Hodge

\begin{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$. \end{conjecture}

Keywords: Hodge Theory; Millenium Problems

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $G$, let $cp(G)$ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $cc(G)$ denote the cardinality of a minimum feedback vertex set (set of vertices $X$ so that $G-X$ is acyclic).

\begin{conjecture} For every planar graph $G$, $cc(G)\leq 2cp(G)$. \end{conjecture}

Keywords: cycle packing; feedback vertex set; planar graph

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

\begin{conjecture} Every digraph in which each vertex has outdegree at least $k$ contains $k$ directed cycles $C_1, \ldots, C_k$ such that $C_j$ meets $\cup_{i=1}^{j-1}C_i$ in at most one vertex, $2 \leq j \leq k$. \end{conjecture}

Keywords:

The permanent conjecture ★★

Author(s): Kahn

\begin{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. \end{conjecture}

Keywords: invertible; matrix; permanent

3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

\begin{question} Is the set of Fibonacci numbers 3-accessible? \end{question}

Keywords: Fibonacci numbers; monochromatic diffsequences

Long rainbow arithmetic progressions ★★

Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic

For $k\in \mathbb{N}$ let $T_k$ denote the minimal number $t\in \mathbb{N}$ such that there is a rainbow $AP(k)$ in every equinumerous $t$-coloring of $\{ 1,2,\ldots ,tn\}$ for every $n\in \mathbb{N}$

\begin{conjecture} For all $k\geq 3$, $T_k=\Theta (k^2)$. \end{conjecture}

Keywords: arithmetic progression; rainbow

Which lattices occur as intervals in subgroup lattices of finite groups? ★★★★

Author(s):

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. There exists a finite lattice that is not an interval in the subgroup lattice of a finite group. \end{conjecture}

Keywords: congruence lattice; finite groups

Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

\begin{problem} Does the following equality hold for every graph $G$? \[ \text{pair-cr}(G) = \text{cr}(G) \] \end{problem}

The \Def[crossing number]{Crossing number (graph theory)} $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the \emph{pairwise crossing number} $\text{pair-cr}(G)$, we minimize the number of pairs of edges that cross. %and the \emph{odd-crossing number} $(\text{odd-cr}(G))$ counts the minimum %number of pairs of edges that cross an odd number of times.

Keywords: crossing number; pair-crossing number

Separators in string graphs ★★

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

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

Keywords: separator; string graphs

3-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every 4-\Def[edge-connected]{connectivity (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 3-flow. \end{conjecture}

Keywords: nowhere-zero flow

Criterion for boundedness of power series

Author(s): Rüdinger

\begin{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}$. \end{question}

Keywords: boundedness; power series; real analysis

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

\begin{conjecture} Every metamonovalued reloid is monovalued. \end{conjecture}

Keywords:

A sextic counterexample to Euler's sum of powers conjecture ★★

Author(s): Euler

\begin{problem} Find six positive integers $x_1, x_2, \dots, x_6$ such that $$x_1^6 + x_2^6 + x_3^6 + x_4^6 + x_5^6 = x_6^6$$ or prove that such integers do not exist. \end{problem}

Keywords:

Growth of finitely presented groups ★★★

Author(s): Adyan

\begin{problem} Does there exist a finitely presented group of intermediate growth? \end{problem}

Keywords: finitely presented; growth

Seymour's r-graph conjecture ★★★

Author(s): Seymour

An $r$-\emph{graph} is an $r$-regular graph $G$ with the property that $|\delta(X)| \ge r$ for every $X \subseteq V(G)$ with odd size.

\begin{conjecture} $\chi'(G) \le r+1$ for every $r$-graph $G$. \end{conjecture}

Keywords: edge-coloring; r-graph

Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

\begin{conjecture} % Enter your conjecture in LaTeX For all $n > 2$, there exist positive integers $x$, $y$, $z$ such that $$1/x + 1/y + 1/z = 4/n$$. % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: Egyptian fraction

Slice-ribbon problem ★★★★

Author(s): Fox

\begin{conjecture} Given a knot in $S^3$ which is slice, is it a ribbon knot? % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: cobordism; knot; ribbon; slice

Saturated $k$-Sperner Systems of Minimum Size ★★

Author(s): Morrison; Noel; Scott

\begin{question} Does there exist a constant $c>1/2$ and a function $n_0(k)$ such that if $|X|\geq n_0(k)$, then every saturated $k$-Sperner system $\mathcal{F}\subseteq \mathcal{P}(X)$ has cardinality at least $2^{(1+o(1))ck}$? \end{question}

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

Negative association in uniform forests ★★

Author(s): Pemantle

\begin{conjecture} Let $G$ be a finite graph, let $e,f \in E(G)$, and let $F$ be the edge set of a forest chosen uniformly at random from all forests of $G$. Then \[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \] \end{conjecture}

Keywords: forest; negative association

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

\begin{question} Does there exist a 57-\Def[regular]{regular graph} graph with \Def[diameter]{diameter (graph theory)} 2 and \Def{girth} 5? \end{question}

Keywords: cage; Moore graph

General position subsets ★★

Author(s): Gowers

\begin{question} What is the least integer $f(n)$ such that every set of at least $f(n)$ points in the plane contains $n$ collinear points or a subset of $n$ points in general position (no three collinear)? \end{question}

Keywords: general position subset, no-three-in-line problem

Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

\begin{problem} Prove \emph{unconditionally} that \Def[$\mathcal{AM}$]{Arthur-Merlin_protocol} $\subseteq$ \Def[$\Sigma_2$]{Polynomial_hierarchy}. \end{problem}

Keywords: Arthur-Merlin; Hitting Sets; unconditional

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

Author(s): Haythorpe

\begin{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$? \end{conjecture}

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

Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

\begin{question} Is there a constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^tn$ cliques? \end{question}

Keywords: clique; graph; minor

Partial List Coloring ★★★

Author(s): Iradmusa

Let $G$ be a simple graph, and for every list assignment $\mathcal{L}$ let $\lambda_{\mathcal{L}}$ be the maximum number of vertices of $G$ which are colorable with respect to $\mathcal{L}$. Define $\lambda_t = \min{ \lambda_{\mathcal{L}} }$, where the minimum is taken over all list assignments $\mathcal{L}$ with $|\mathcal{L}| = t$ for all $v \in V(G)$.

\begin{conjecture} [2] Let $G$ be a graph with list chromatic number $\chi_\ell$ and $1\leq r\leq s\leq \chi_\ell$. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\] \end{conjecture}

Keywords: list assignment; list coloring

The Two Color Conjecture ★★

Author(s): Neumann-Lara

\begin{conjecture} If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i$ is acyclic for $i=1,2$. \end{conjecture}

Keywords: acyclic; digraph; planar

Fractional Hadwiger ★★

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

\begin{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)$. \end{conjecture}

Keywords: fractional coloring, minors

Strong matchings and covers ★★★

Author(s): Aharoni

Let $H$ be a \Def{hypergraph}. A \emph{strongly maximal} matching is a matching $F \subseteq E(H)$ so that $|F' \setminus F| \le |F \setminus F'|$ for every matching $F'$. A \emph{strongly minimal} cover is a (vertex) cover $X \subseteq V(H)$ so that $|X' \setminus X| \ge |X \setminus X'|$ for every cover $X'$.

\begin{conjecture} If $H$ is a (possibly infinite) hypergraph in which all edges have size $\le k$ for some integer $k$, then $H$ has a strongly maximal matching and a strongly minimal cover. \end{conjecture}

Keywords: cover; infinite graph; matching

Mixing Circular Colourings

Author(s): Brewster; Noel

\begin{question} Is $\mathfrak{M}_c(G)$ always rational? \end{question}

Keywords: discrete homotopy; graph colourings; mixing

Shannon capacity of the seven-cycle ★★★

Author(s):

\begin{problem} What is the Shannon capacity of $C_7$? \end{problem}

Keywords:

Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

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

\begin{conjecture} $\displaystyle cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2} \floor{\frac n2} \floor{\frac {n-1}2} $ \end{conjecture}

Keywords: complete bipartite graph; crossing number

Choosability of Graph Powers ★★

Author(s): Noel

\begin{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)?\] \end{question}

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

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

\begin{conjecture} Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of $K_n$ linear in $n$? \end{conjecture}

Keywords: complete graph; edge coloring; star coloring

Subset-sums equality (pigeonhole version) ★★★

Author(s):

\begin{problem} Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist distinct subsets $I,J \subseteq \{1,\ldots,n\}$ with $\sum_{i \in I} a_i = \sum_{j \in J} a_j$. Is it possible to find such a pair $I,J$ in polynomial time? \end{problem}

Keywords: polynomial algorithm; search problem

Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

\begin{conjecture} If $G$ is a $k$-regular directed graph with no parallel arcs, then $G$ contains a collection of ${k+1 \choose 2}$ arc-disjoint directed cycles. \end{conjecture}

Keywords:

Subgroup formed by elements of order dividing n ★★

Author(s): Frobenius

\begin{conjecture}

Suppose $G$ is a finite group, and $n$ is a positive integer dividing $|G|$. Suppose that $G$ has exactly $n$ solutions to $x^{n} = 1$. Does it follow that these solutions form a subgroup of $G$?

\end{conjecture}

Keywords: order, dividing

Quartic rationally derived polynomials ★★★

Author(s): Buchholz; MacDougall

Call a polynomial $p \in {\mathbb Q}[x]$ \emph{rationally derived} if all roots of $p$ and the nonzero derivatives of $p$ are rational.

\begin{conjecture} There does not exist a quartic rationally derived polynomial $p \in {\mathbb Q}[x]$ with four distinct roots. \end{conjecture}

Keywords: derivative; diophantine; elliptic; polynomial

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

\begin{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)$.

\end{conjecture}

Keywords: Pierce expansions

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

\begin{conjecture} Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane. \end{conjecture}

Keywords: Hypergraphs

The Riemann Hypothesis ★★★★

Author(s): Riemann

The zeroes of the Riemann zeta function that are inside the Critical Strip (i.e. the vertical strip of the complex plane where the real part of the complex variable is in ]0;1[), are actually located on the Critical line ( the vertical line of the complex plane with real part equal to 1/2)

Keywords: Millenium Problems; zeta

Weak saturation of the cube in the clique

Author(s): Morrison; Noel

\begin{problem} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Determine $\text{wsat}(K_n,Q_3)$. \end{problem}

Keywords: bootstrap percolation; hypercube; Weak saturation