Random

Caccetta-Häggkvist Conjecture ★★★★

Author(s): Caccetta; Häggkvist

\begin{conjecture} Every simple digraph of order $n$ with minimum outdegree at least $r$ has a cycle with length at most $\lceil n/r\rceil$ \end{conjecture}

Keywords:

The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

\begin{conjecture}[BEC-conjecture] If $G_1$ and $G_2$ are $n$-vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$, then $G_1$ and $G_2$ pack. \end{conjecture}

Keywords: graph packing

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)$.

\begin{conjecture} The following statements are equivalent for every endofuncoid $\mu$ and a set $U$: \begin{enumerate} \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$. \end{enumerate} \end{conjecture}

Keywords: connected; connectedness; proximity space

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $G$ is $k$-\emph{degenerate} if every subgraph of $G$ has a vertex of degree $\le k$.

\begin{conjecture} Every simple planar graph has a 5-coloring so that for $1 \le k \le 4$, the union of any $k$ color classes induces a $(k-1)$-degenerate graph. \end{conjecture}

Keywords: coloring; degenerate; planar

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

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

\begin{problem} for every graph $G$, we let $L(G)$ denote the \Def{line graph} of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$? \end{problem}

Keywords: reconstruction; tree

Termination of the sixth Goodstein Sequence

Author(s): Graham

\begin{question} How many steps does it take the sixth Goodstein sequence to terminate? \end{question}

Keywords: Goodstein Sequence

Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

\begin{conjecture} Every planar graph on $n$ verices has an induced forest with at least $n/2$ vertices. \end{conjecture}

Keywords:

P vs. BPP ★★★

Author(s): Folklore

\begin{conjecture} Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP? \end{conjecture}

Keywords: BPP; circuit complexity; pseudorandom generators

Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let $C$ be a class of finite relational structures. We denote by $f_C(n)$ the number of structures in $C$ over the labeled set $\{0, \dots, n-1 \}$. For any class $C$ definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every $m \in \mathbb{N}$, the function $f_C(n)$ is ultimately periodic modulo $m$.

\begin{question} Does the Blatter-Specker Theorem hold for ternary relations. \end{question}

Keywords: Blatter-Specker Theorem; FMT00-Luminy

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

Author(s): Erdos; Turan

Let $B \subseteq {\mathbb N}$. The \emph{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 \emph{additive basis} if $r_B$ is never $0$.

\begin{conjecture} If $B$ is an additive basis, then $r_B$ is unbounded. \end{conjecture}

Keywords: additive basis; representation function

Dense rational distance sets in the plane ★★★

Author(s): Ulam

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

Keywords: integral distance; rational distance

P vs. NP ★★★★

Author(s): Cook; Levin

\begin{problem} Is P = NP? \end{problem}

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

Durer's Conjecture ★★★

Author(s): Durer; Shephard

\begin{conjecture} Every convex polytope has a non-overlapping edge unfolding. \end{conjecture}

Keywords: folding; polytope

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.

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

Keywords:

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 strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

\begin{conjecture} There exists an ineteger $k$ so that every $k$-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs? \end{conjecture}

Keywords:

Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

\begin{problem} Can $O(n)$-size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$, $f(0x) = 0f(x)$, $f(1x) = 1f(x)$, and $f(2x) = f(x)2$? \end{problem}

Keywords: Circuits; sorting

Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

\begin{conjecture} If $G$ has at most $k$ edge-disjoint triangles, then there is a set of $2k$ edges whose deletion destroys every triangle. \end{conjecture}

Keywords:

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

\begin{conjecture} Every bridgeless cubic graph has two perfect matchings $M_1$, $M_2$ so that $M_1 \cap M_2$ does not contain an odd edge-cut. \end{conjecture}

Keywords: cubic; nowhere-zero flow; perfect matching

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

\begin{conjecture} Every 6-\Def[connected]{connectivity (graph theory)} graph without a \Def[$K_6$]{complete graph} \Def[minor]{minor (graph theory)} is apex (planar plus one vertex). \end{conjecture}

Keywords: connectivity; minor

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

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

Keywords: list assignment; list coloring

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

Author(s): Thomassen

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

Keywords:

Turán's problem for hypergraphs ★★

Author(s): Turan

\begin{conjecture} Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges. \end{conjecture}

\begin{conjecture} Every simple $3$-uniform hypergraph on $2n$ vertices which contains no complete $3$-uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges. \end{conjecture}

Keywords:

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

5-flow conjecture ★★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 5-flow. \end{conjecture}

Keywords: cubic; nowhere-zero flow

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

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

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

Keywords: induced subgraph

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

\begin{question} Is every \Def{Cayley graph} Hamiltonian? \end{question}

Keywords:

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

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

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

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

Random stable roommates ★★

Author(s): Mertens

\begin{conjecture} The probability that a random instance of the stable roommates problem on $n \in 2{\mathbb N}$ people admits a solution is $\Theta( n ^{-1/4} )$. \end{conjecture}

Keywords: stable marriage; stable roommates

Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

\begin{conjecture} Every strong oriented graph in which each vertex has indegree and outdegree at least $d$ contains a directed cycle of length at least $2d+1$. \end{conjecture}

Keywords:

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

Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

\begin{conjecture} There exists an integer $k$ such that every $k$-arc-strong digraph $D$ with specified vertices $u$ and $v$ contains an out-branching rooted at $u$ and an in-branching rooted at $v$ which are arc-disjoint.

% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

\begin{question} Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large? \end{question}

Keywords: choosability; list coloring; on-line choosability

Kriesell's Conjecture ★★

Author(s): Kriesell

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

Keywords: Disjoint paths; edge-connectivity; spanning trees

Graph product of multifuncoids ★★

Author(s): Porton

\begin{conjecture} Let $F$ is a family of multifuncoids such that each $F_i$ is of the form $\lambda j \in N \left( i \right) : \mathfrak{F} \left( U_j \right)$ where $N \left( i \right)$ is an index set for every $i$ and $U_j$ is a set for every $j$. Let every $F_i = E^{\ast} f_i$ for some multifuncoid $f_i$ of the form $\lambda j \in N \left( i \right) : \mathfrak{P} \left( U_j \right)$ regarding the filtrator $\left( \prod_{j \in N \left( i \right)} \mathfrak{F} \left( U_j \right) ; \prod_{j \in N \left( i \right)} \mathfrak{P} \left( U_j \right) \right)$. Let $H$ is a graph-composition of $F$ (regarding some partition $G$ and external set $Z$). Then there exist a multifuncoid $h$ of the form $\lambda j \in Z : \mathfrak{P} \left( U_j \right)$ such that $H = E^{\ast} h$ regarding the filtrator $\left( \prod_{j \in Z} \mathfrak{F} \left( U_j \right) ; \prod_{j \in Z} \mathfrak{P} \left( U_j \right) \right)$. \end{conjecture}

Keywords: graph-product; multifuncoid

Chowla's cosine problem ★★★

Author(s): Chowla

\begin{problem} Let $A \subseteq {\mathbb N}$ be a set of $n$ positive integers and set \[m(A) = - \min_x \sum_{a \in A} \cos(ax).\] What is $m(n) = \min_A m(A)$? \end{problem}

Keywords: circle; cosine polynomial

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

Author(s): Gyarfas

Say that a family ${\mathcal F}$ of graphs is $\chi$-\emph{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))$.

\begin{conjecture} For every fixed tree $T$, the family of graphs with no induced subgraph isomorphic to $T$ is $\chi$-bounded. \end{conjecture}

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

Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

\begin{problem} Does every connected \Def{vertex-transitive graph} have a \Def{Hamiltonian path}? \end{problem}

Keywords: cycle; hamiltonian; path; vertex-transitive

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

\begin{conjecture} Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having precisely $n$ spanning trees. Then $ \alpha(n) = o(\log{n}).$ \end{conjecture}

Keywords: number of spanning trees, asymptotics

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

\begin{conjecture} For every $\epsilon > 0$ and every positive integer $k$, there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$-regular graph $G$ with $r \ge r_0$ has a $k$-regular subgraph $H$ with $|V(H)| \ge (1- \epsilon) |V(G)|$. \end{conjecture}

Keywords: regular; subgraph

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

Chromatic number of associahedron ★★

Author(s): Fabila-Monroy; Flores-Penaloza; Huemer; Hurtado; Urrutia; Wood

\begin{conjecture} Associahedra have unbounded chromatic number. \end{conjecture}

Keywords: associahedron, graph colouring, chromatic number

Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

\begin{problem} Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{problem}

Keywords: 3-manifold; 4-sphere; embedding

S(S(f)) = S(f) for reloids ★★

Author(s): Porton

\begin{question} $S(S(f)) = S(f)$ for every endo-\href[reloid]{http://www.wikinfo.org/index.php/Reloid} $f$? \end{question}

Keywords: reloid

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:

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An \emph{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 \emph{universal} if for every pair of edges $e,f$, there is an alternating walk containing both $e$ and $f$

\begin{question} Does there exist a locally finite highly arc transitive digraph which is universal? \end{question}

Keywords: arc transitive; digraph

Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbers such that $1 \leq |\phi(e)| \leq r-1$, for all $e \in E(G)$, and $\sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G)$. The circular flow number of $G$ is inf$\{ r | G$ has a nowhere-zero $r$-flow $\}$, and it is denoted by $F_c(G)$.

A graph with maximum vertex degree $k$ is a class 1 graph if its edge chromatic number is $k$.

\begin{conjecture} Let $t \geq 1$ be an integer and $G$ a $(2t+1)$-regular graph. If $G$ is a class 1 graph, then $F_c(G) \leq 2 + \frac{2}{t}$. \end{conjecture}

Keywords: nowhere-zero flow, edge-colorings, regular graphs