Random

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

Author(s): Morrison; Noel

Problem   Determine the smallest percolating set for the $ 4 $-neighbour bootstrap process in the hypercube.

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

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.

Conjecture   Let $ D $ be a digraph. If $ |A(D)| > (k-2) |V(D)| $, then $ D $ contains every antidirected tree of order $ k $.

Keywords:

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $ G $, we let $ \gamma(G) $ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $ \beta(G) $ be the size of the smallest feedback edge set.

Conjecture  If $ G $ is a simple digraph without directed cycles of length $ \le 3 $, then $ \beta(G) \le \frac{1}{2} \gamma(G) $.

Keywords: acyclic; digraph; feedback edge set; triangle free

Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

Conjecture   $ p $ is a prime iff $ ~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p $

Keywords: primality

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

Problem   Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $ r > 2 $?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

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

Is Skewes' number e^e^e^79 an integer? ★★

Author(s):

Conjecture  

Skewes' number $ e^{e^{e^{79}}} $ is not an integer.

Keywords:

Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

Question   What is the minimum number of colours such that every complete geometric graph on $ n $ vertices has an edge colouring such that:
    \item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

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

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Author(s): Mader

Conjecture   For all $ k $ there is an integer $ f(k) $ such that every digraph of minimum outdegree at least $ f(k) $ contains a subdivision of a transitive tournament of order $ k $.

Keywords:

Every metamonovalued reloid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued reloid is monovalued.

Keywords:

The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

Conjecture   For every positive integer $ k $, every digraph with minimum out-degree at least $ 2k-1 $ contains $ k $ disjoint cycles.

Keywords: cycles

End-Devouring Rays

Author(s): Georgakopoulos

Problem   Let $ G $ be a graph, $ \omega $ a countable end of $ G $, and $ K $ an infinite set of pairwise disjoint $ \omega $-rays in $ G $. Prove that there is a set $ K' $ of pairwise disjoint $ \omega $-rays that devours $ \omega $ such that the set of starting vertices of rays in $ K' $ equals the set of starting vertices of rays in $ K $.

Keywords: end; ray

Circular flow numbers of $r$-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) $.

A $ (2t+1) $-regular graph $ G $ is a $ (2t+1) $-graph if $ |\partial_G(X)| \geq 2t+1 $ for every $ X \subseteq V(G) $ with $ |X| $ odd.

Conjecture   Let $ t > 1 $ be an integer. If $ G $ is a $ (2t+1) $-graph, then $ F_c(G) \leq 2 + \frac{2}{t} $.

Keywords: flow conjectures; nowhere-zero flows

Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

Problem   Let $ M $ be a $ 3 $-dimensional smooth submanifold of $ S^4 $, $ M $ diffeomorphic to $ S^3 $. By the Jordan-Brouwer separation theorem, $ M $ separates $ S^4 $ into the union of two compact connected $ 4 $-manifolds which share $ M $ as a common boundary. The Schoenflies problem asks, are these $ 4 $-manifolds diffeomorphic to $ D^4 $? ie: is $ M $ unknotted?

Keywords: 4-dimensional; Schoenflies; sphere

¿Are critical k-forests tight? ★★

Author(s): Strausz

Conjecture  

Let $ H $ be a $ k $-uniform hypergraph. If $ H $ is a critical $ k $-forest, then it is a $ k $-tree.

Keywords: heterochromatic number

Separators in string graphs ★★

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

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

Keywords: separator; string graphs

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

Conjecture   The following statements are equivalent for every endofuncoid $ \mu $ and a set $ U $:
    \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 $.

Keywords: connected; connectedness; proximity space

Unit vector flows ★★

Author(s): Jain

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

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.

Keywords: nowhere-zero flow

Outer reloid of restricted funcoid ★★

Author(s): Porton

Question   $ ( \mathsf{RLD})_{\mathrm{out}} (f \cap^{\mathsf{FCD}} ( \mathcal{A} \times^{\mathsf{FCD}} \mathcal{B})) = (( \mathsf{RLD})_{\mathrm{out}} f) \cap^{\mathsf{RLD}} ( \mathcal{A} \times^{\mathsf{RLD}} \mathcal{B}) $ for every filter objects $ \mathcal{A} $ and $ \mathcal{B} $ and a funcoid $ f\in\mathsf{FCD}(\mathrm{Src}\,f; \mathrm{Dst}\,f) $?

Keywords: direct product of filters; outer reloid

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

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

Perfect cuboid ★★

Author(s):

Conjecture   Does a perfect cuboid exist?

Keywords:

Decomposing eulerian graphs ★★★

Author(s):

Conjecture   If $ G $ is a 6-edge-connected Eulerian graph and $ P $ is a 2-transition system for $ G $, then $ (G,P) $ has a compaible decomposition.

Keywords: cover; cycle; Eulerian

Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

Conjecture   For every positive integer $ t $, every (loopless) graph $ G $ with $ \chi(G) \ge t $ immerses $ K_t $.

Keywords: coloring; complete graph; immersion

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture   If $ G $ is a non-empty graph containing no induced odd cycle of length at least $ 5 $, then there is a $ 2 $-vertex colouring of $ G $ in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

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

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

Author(s): Yuster

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.

Keywords:

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

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}.\]

Keywords: list assignment; list coloring

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

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

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

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

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:

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem   Find a constant $ k $ such that for any $ d $ there is a sequence of tautologies of depth $ k $ that have polynomial (or quasi-polynomial) size proofs in depth $ d+1 $ Frege system $ F_{d+1} $ but requires exponential size $ F_d $ proofs.

Keywords: Frege system; short proof

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $ P \subseteq {\mathbb R}^2 $ is $ n $-universal if every $ n $ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $ P $, and all edges are (non-intersecting) straight line segments.

Question   Does there exist an $ n $-universal set of size $ O(n) $?

Keywords: geometric graph; planar graph; universal set

Turán's problem for hypergraphs ★★

Author(s): Turan

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

Keywords:

Goldberg's conjecture ★★★

Author(s): Goldberg

The overfull parameter is defined as follows: \[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]

Conjecture   Every graph $ G $ satisfies $ \chi'(G) \le \max\{ \Delta(G) + 1, w(G) \} $.

Keywords: edge-coloring; multigraph

$C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any $ C^r $ structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $ S_n $ denote the set of all permutations of $ [n]=\set{1,2,\ldots,n} $. Let $ i(\pi) $ and $ d(\pi) $ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $ \pi $. Let $ X(\pi) $ denote the set of subsequences of $ \pi $ with length at least three. Let $ t(\pi) $ denote $ \sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)) $.

A permutation $ \pi\in S_n $ is called a Roller Coaster permutation if $ t(\pi)=\max_{\tau\in S_n}t(\tau) $. Let $ RC(n) $ be the set of all Roller Coaster permutations in $ S_n $.

Conjecture   For $ n\geq 3 $,
    \item If $ n=2k $, then $ |RC(n)|=4 $. \item If $ n=2k+1 $, then $ |RC(n)|=2^j $ with $ j\leq k+1 $.
Conjecture  (Odd Sum conjecture)   Given $ \pi\in RC(n) $,
    \item If $ n=2k+1 $, then $ \pi_j+\pi_{n-j+1} $ is odd for $ 1\leq j\leq k $. \item If $ n=2k $, then $ \pi_j + \pi_{n-j+1} = 2k+1 $ for all $ 1\leq j\leq k $.

Keywords:

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

Weak pentagon problem ★★

Author(s): Samal

Conjecture   If $ G $ is a cubic graph not containing a triangle, then it is possible to color the edges of $ G $ by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

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

Á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:

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem   Does there exist a polynomial time algorithm which takes as input a graph $ G $ and for every vertex $ v \in V(G) $ a subset $ \ell(v) $ of $ \{1,2,3,4\} $, and decides if there exists a partition of $ V(G) $ into $ \{A_1,A_2,A_3,A_4\} $ so that $ v \in A_i $ only if $ i \in \ell(v) $ and so that $ A_1,A_2 $ are independent, $ A_4 $ is a clique, and there are no edges between $ A_1 $ and $ A_3 $?

Keywords: list partition; polynomial algorithm

Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

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

Keywords: curvature; polytope