Random

Are almost all graphs determined by their spectrum? ★★★

Author(s):

\begin{problem} Are almost all graphs uniquely determined by the spectrum of their adjacency matrix? \end{problem}

Keywords: cospectral; graph invariant; spectrum

Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

\begin{conjecture} The average diameter of a bounded cell of a simple arrangement defined by $n$ hyperplanes in dimension $d$ is not greater than $d$. \end{conjecture}

Keywords: arrangement; diameter; polytope

Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

\begin{question} Are there any switching-nonreconstructible digraphs on twelve or more vertices? \end{question}

Keywords:

A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order $\sqsubseteq$:

  1. $\Phi_{\ast} f = \lambda b \in \mathfrak{B}: \bigcup \{ x \in \mathfrak{A} \mid f x \sqsubseteq b \}$;
  2. $\Phi^{\ast} f = \lambda b \in \mathfrak{A}: \bigcap \{ x \in \mathfrak{B} \mid f x \sqsupseteq b \}$.

Note that the above is a generalization of monotone Galois connections (with $\max$ and $\min$ replaced with suprema and infima).

Then we have the following diagram:

\Image{diagram2.png}

What is at the node "other" in the diagram is unknown.

\begin{conjecture} "Other" is $\lambda f\in\mathsf{FCD}: \top$. \end{conjecture}

\begin{question} What repeated applying of $\Phi_{\ast}$ and $\Phi^{\ast}$ to "other" leads to? Particularly, does repeated applying $\Phi_{\ast}$ and/or $\Phi^{\ast}$ to the node "other" lead to finite or infinite sets? \end{question}

Keywords: Galois connections

r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

\begin{conjecture} If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian. \end{conjecture}

Keywords: hamiltonian; regular; uniquely hamiltonian

Which homology 3-spheres bound homology 4-balls? ★★★★

Author(s): Ancient/folklore

\begin{problem} Is there a complete and computable set of invariants that can determine which (rational) homology $3$-spheres bound (rational) homology $4$-balls? % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{problem}

Keywords: cobordism; homology ball; homology sphere

Cube-Simplex conjecture ★★★

Author(s): Kalai

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

Keywords: cube; facet; polytope; simplex

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

Odd-cycle transversal in triangle-free graphs ★★

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

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

Keywords:

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

\begin{conjecture} If $T$ is a tournament of order $n$, then it contains $\left \lceil n(n-1)/6 - n/3\right\rceil$ arc-disjoint transitive subtournaments of order 3. \end{conjecture}

Keywords:

Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The \emph{fatness} of a 4-\Def{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$.

\begin{question} Does there exist a fixed constant $c$ so that every convex 4-polytope has fatness at most $c$? \end{question}

Keywords: f-vector; polytope

Laplacian Degrees of a Graph ★★

Author(s): Guo

\begin{conjecture} If $G$ is a connected graph on $n$ vertices, then $c_k(G) \ge d_k(G)$ for $k = 1, 2, \dots, n-1$. \end{conjecture}

Keywords: degree sequence; Laplacian matrix

Primitive pythagorean n-tuple tree ★★

Author(s):

\begin{conjecture} Find linear transformation construction of primitive pythagorean n-tuple tree! % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

\begin{conjecture} For every $0 \le t \le n-1$, the sequence in ${\mathbb Z}_n^2$ consisting of $n-1$ copes of $(1,0)$ and $t$ copies of $(0,1)$ has the fewest number of distinct subsequence sums over all zero-free sequences from ${\mathbb Z}_n^2$ of length $n-1+t$. \end{conjecture}

Keywords: subsequence sum; zero sum

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

\begin{conjecture} If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$ \end{conjecture}

Keywords: Inequality; Probability Theory; randomness in TCS

Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

\begin{conjecture} \begin{enumerate} \item If $G$ is a countable connected graph then its third \Def[power]{Glossary_of_graph_theory#Distance} is hamiltonian. \item If $G$ is a 2-connected countable graph then its square is hamiltonian. \end{enumerate} \end{conjecture}

Keywords: hamiltonian; infinite graph

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

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

\begin{conjecture} If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$. \end{conjecture}

Here $G \times H$ is the \Def[tensor product]{tensor product of graphs} (also called the direct or categorical product) of $G$ and $H$.

Keywords: categorical product; coloring; homomorphism; tensor product

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

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

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 \emph{visible} with respect to $S$ if the line segment between $v$ and $w$ contains no other point in $S$.

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

Keywords: Discrete Geometry; Geometric Ramsey Theory

Triangle free strongly regular graphs ★★★

Author(s):

\begin{problem} Is there an eighth triangle free strongly regular graph? \end{problem}

Keywords: strongly regular; triangle free

Nonrepetitive colourings of planar graphs ★★

Author(s): Alon N.; Grytczuk J.; Hałuszczak M.; Riordan O.

\begin{question} Do planar graphs have bounded nonrepetitive chromatic number? \end{question}

Keywords: nonrepetitive colouring; planar graphs

A conjecture about direct product of funcoids ★★

Author(s): Porton

\begin{conjecture} Let $f_1$ and $f_2$ are monovalued, entirely defined funcoids with $\operatorname{Src}f_1=\operatorname{Src}f_2=A$. Then there exists a pointfree funcoid $f_1 \times^{\left( D \right)} f_2$ such that (for every filter $x$ on $A$) $$\left\langle f_1 \times^{\left( D \right)} f_2 \right\rangle x = \bigcup \left\{ \langle f_1\rangle X \times^{\mathsf{FCD}} \langle f_2\rangle X \hspace{1em} | \hspace{1em} X \in \mathrm{atoms}^{\mathfrak{A}} x \right\}.$$ (The join operation is taken on the lattice of filters with reversed order.) \end{conjecture}

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

Decomposition of completions of reloids ★★

Author(s): Porton

\begin{conjecture} For composable reloids $f$ and $g$ it holds \begin{enumerate} \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)$. \end{enumerate} \end{conjecture}

Keywords: co-completion; completion; reloid

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

Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

\begin{problem} Does for every integer $N$ exist a \Def{covering system} with all moduli distinct and at least equal to~$N$? \end{problem}

Keywords: covering system

Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

\begin{question} Is the chromatic number of a random lift of $K_5$ concentrated on a single value? \end{question}

Keywords: random lifts, coloring

Total Colouring Conjecture ★★★

Author(s): Behzad

\begin{conjecture} A total coloring of a graph $G = (V,E)$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $G$, $\chi''(G)$, equals the minimum number of colors needed in a total coloring of $G$. It is an old conjecture of Behzad that for every graph $G$, the total chromatic number equals the maximum degree of a vertex in $G$, $\Delta(G)$ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\] \end{conjecture}

Keywords: Total coloring

Covering a square with unit squares ★★

Author(s):

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

Keywords:

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

\begin{conjecture} If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$) so that the resulting matrix has all eigenvalues of magnitude at most $2 \sqrt{d-1}$. \end{conjecture}

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

Order-invariant queries ★★

Author(s): Segoufin

\begin{question} \begin{enumerate} \item Does ${<}\text{-invariant\:FO} = \text{FO}$ hold over graphs of bounded tree-width? \item Is ${<}\text{-invariant\:FO}$ included in $\text{MSO}$ over graphs? \item Does ${<}\text{-invariant\:FO}$ have a 0-1 law? \item Are properties of ${<}\text{-invariant\:FO}$ Hanf-local? \item Is there a logic (with an effective syntax) that captures ${<}\text{-invariant\:FO}$? \end{enumerate} \end{question}

Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

\begin{conjecture} Let $C$ be a circuit in a bridgeless cubic graph $G$. Then there is a five cycle double cover of $G$ such that $C$ is a subgraph of one of these five cycles. \end{conjecture}

Keywords: cycle cover

Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

\begin{conjecture} Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$, then $D$ contains every antidirected tree of order $k$. \end{conjecture}

Keywords:

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

\begin{problem} Let $k_1, \dots , k_p$ be positve integer Does there exists an integer $g(k_1, \dots , k_p)$ such that every $g(k_1, \dots , k_p)$-strong tournament $T$ admits a partition $(V_1\dots , V_p)$ of its vertex set such that the subtournament induced by $V_i$ is a non-trivial $k_i$-strong for all $1\leq i\leq p$. \end{problem}

Keywords:

Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

\begin{problem} Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$? \end{problem}

Keywords: circular coloring; planar graph; triangle free

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

The three 4-flows conjecture ★★

Author(s): DeVos

\begin{conjecture} For every graph $G$ with no \Def[bridge]{bridge (graph theory)}, there exist three disjoint sets $A_1,A_2,A_3 \subseteq E(G)$ with $A_1 \cup A_2 \cup A_3 = E(G)$ so that $G \setminus A_i$ has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow for $1 \le i \le 3$. \end{conjecture}

Keywords: nowhere-zero flow

Packing T-joins ★★

Author(s): DeVos

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

Keywords: packing; T-join

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

\begin{conjecture} Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles. \end{conjecture}

Keywords:

Lonely runner conjecture ★★★

Author(s): Cusick; Wills

\begin{conjecture} Suppose $k$ runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least $\frac{1}{k}$ (along the track) away from every other runner. \end{conjecture}

Keywords: diophantine approximation; view obstruction

Chords of longest cycles ★★★

Author(s): Thomassen

\begin{conjecture} If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord. \end{conjecture}

Keywords: chord; connectivity; cycle

Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

\begin{conjecture} Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees. \end{conjecture}

Keywords: complete geometric graph, edge colouring

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

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

Keywords:

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

Are there an infinite number of lucky primes?

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

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

Keywords: lucky; prime; seive

Petersen coloring conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Let $G$ be a \Def[cubic]{cubic graph} graph with no \Def[bridge]{bridge (graph theory)}. Then there is a coloring of the edges of $G$ using the edges of the \Def[Petersen]{petersen graph} graph so that any three mutually adjacent edges of $G$ map to three mutually adjancent edges in the Petersen graph. \end{conjecture}

Keywords: cubic; edge-coloring; Petersen graph

Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

\begin{conjecture} Every digraph has a stable set meeting all longest directed paths \end{conjecture}

Keywords:

List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

\begin{conjecture} Every $K_t$-minor-free graph is $c t$-list-colourable for some constant $c\geq1$. \end{conjecture}

Keywords: Hadwiger conjecture; list colouring; minors

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: