Random

Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let $ Q_d $ denote the $ d $-dimensional cube graph. A map $ \phi : E(Q_d) \rightarrow \{0,1\} $ is called edge-antipodal if $ \phi(e) \neq \phi(e') $ whenever $ e,e' $ are antipodal edges.

Conjecture   If $ d \ge 2 $ and $ \phi : E(Q_d) \rightarrow \{0,1\} $ is edge-antipodal, then there exist a pair of antipodal vertices $ v,v' \in V(Q_d) $ which are joined by a monochromatic path.

Keywords: antipodal; cube; edge-coloring

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

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let $ (a_0,a_1,a_2,\ldots,0) $ be a sequence of nonnegative integers which strictly decreases until $ 0 $.

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus $ i $ with $ a_i $ crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

Strong matchings and covers ★★★

Author(s): Aharoni

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

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.

Keywords: cover; infinite graph; matching

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

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

Keywords: subsequence sum; zero sum

Algebraic independence of pi and e ★★★

Author(s):

Conjecture   $ \pi $ and $ e $ are algebraically independent

Keywords: algebraic independence

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $ G $ be an (additive) abelian group, and for every $ S \subseteq G $ let $ {\mathit stab}(S) = \{ g \in G : g + S = S \} $.

Conjecture   Let $ M $ be a matroid on $ E $, let $ w : E \rightarrow G $ be a map, put $ S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \} $ and $ H = {\mathit stab}(S) $. Then $$|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$$

Keywords: matroid; sumset; zero sum

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

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

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

Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture   If $ G $ is a simple graph which is the union of $ k $ pairwise edge-disjoint complete graphs, each of which has $ k $ vertices, then the chromatic number of $ G $ is $ k $.

Keywords: chromatic number

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

Keywords: chromatic number; girth; maximum degree; triangle free

Random stable roommates ★★

Author(s): Mertens

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

Keywords: stable marriage; stable roommates

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

MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

Question   Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.

Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages

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

A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture   If $ {\mathbb F} $ is a finite field with at least 4 elements and $ A $ is an invertible $ n \times n $ matrix with entries in $ {\mathbb F} $, then there are column vectors $ x,y \in {\mathbb F}^n $ which have no coordinates equal to zero such that $ Ax=y $.

Keywords: invertible; nowhere-zero flow

5-flow conjecture ★★★★

Author(s): Tutte

Conjecture   Every bridgeless graph has a nowhere-zero 5-flow.

Keywords: cubic; nowhere-zero flow

Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant $ c $ such that every $ n $-vertex $ K_t $-minor-free graph has at most $ c^tn $ cliques?

Keywords: clique; graph; minor

The 4x5 chessboard complex is the complement of a link, which link? ★★

Author(s): David Eppstein

Problem   Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.

Keywords: knot theory, links, chessboard complex

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

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

Keywords: number of spanning trees, asymptotics

Weak saturation of the cube in the clique

Author(s): Morrison; Noel

Problem  

Determine $ \text{wsat}(K_n,Q_3) $.

Keywords: bootstrap percolation; hypercube; Weak saturation

Funcoidal products inside an inward reloid ★★

Author(s): Porton

Conjecture   (solved) If $ a \times^{\mathsf{\ensuremath{\operatorname{RLD}}}} b \subseteq \left( \mathsf{\ensuremath{\operatorname{RLD}}} \right)_{\ensuremath{\operatorname{in}}} f $ then $ a \times^{\mathsf{\ensuremath{\operatorname{FCD}}}} b \subseteq f $ for every funcoid $ f $ and atomic f.o. $ a $ and $ b $ on the source and destination of $ f $ correspondingly.

A stronger conjecture:

Conjecture   If $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{RLD}}}} \mathcal{B} \subseteq \left( \mathsf{\ensuremath{\operatorname{RLD}}} \right)_{\ensuremath{\operatorname{in}}} f $ then $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{FCD}}}} \mathcal{B} \subseteq f $ for every funcoid $ f $ and $ \mathcal{A} \in \mathfrak{F} \left( \ensuremath{\operatorname{Src}}f \right) $, $ \mathcal{B} \in \mathfrak{F} \left( \ensuremath{\operatorname{Dst}}f \right) $.

Keywords: inward reloid

Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by projective plane we mean the set of all lines through the origin in $ \mathbb{R}^3 $.

Definition   Say that a subset $ S $ of the projective plane is octahedral if all lines in $ S $ pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition   Say that a subset $ S $ of the projective plane is weakly octahedral if every set $ S'\subseteq S $ such that $ |S'|=3 $ is octahedral.
Conjecture   Suppose that the projective plane can be partitioned into four sets, say $ S_1,S_2,S_3 $ and $ S_4 $ such that each set $ S_i $ is weakly octahedral. Then each $ S_i $ is octahedral.

Keywords: Partitioning; projective plane

Real roots of the flow polynomial ★★

Author(s): Welsh

Conjecture   All real roots of nonzero flow polynomials are at most 4.

Keywords: flow polynomial; nowhere-zero flow

Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

Conjecture   Every $ 4k $-edge-connected graph can be oriented so that $ {\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0 $ (mod $ 2k+1 $) for every vertex $ v $.

Keywords: nowhere-zero flow; orientation

Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers $ n $ so that both $ n $ and $ n+2 $ are prime.

Keywords: prime; twin prime

Rainbow AP(4) in an almost equinumerous coloring ★★

Author(s): Conlon

Problem   Do 4-colorings of $ \mathbb{Z}_{p} $, for $ p $ a large prime, always contain a rainbow $ AP(4) $ if each of the color classes is of size of either $ \lfloor p/4\rfloor $ or $ \lceil p/4\rceil $?

Keywords: arithmetic progression; rainbow

¿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

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

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

Keywords: complete graph; edge coloring; star coloring

Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger $ k $ so that every $ k $-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Keywords:

Fundamental group torsion for subsets of Euclidean 3-space ★★

Author(s): Ancient/folklore

Problem   Does there exist a subset of $ \mathbb R^3 $ such that its fundamental group has an element of finite order?

Keywords: subsets of euclidean space; torsion

One-way functions exist ★★★★

Author(s):

Conjecture   One-way functions exist.

Keywords: one way function

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

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

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

Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

Problem   If $ G $ is a $ 3 $-connected finite graph, is there an assignment of lengths $ \ell: E(G) \to \mathb R^+ $ to the edges of $ G $, such that every $ \ell $-geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

Strict inequalities for products of filters

Author(s): Porton

Conjecture   $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{RLD}}}}_F \mathcal{B}   \subset \mathcal{A} \ltimes \mathcal{B} \subset \mathcal{A}   \times^{\mathsf{\ensuremath{\operatorname{RLD}}}} \mathcal{B} $ for some filter objects $ \mathcal{A} $, $ \mathcal{B} $. Particularly, is this formula true for $ \mathcal{A} = \mathcal{B} = \Delta \cap \uparrow^{\mathbb{R}} \left( 0 ; +   \infty \right) $?

A weaker conjecture:

Conjecture   $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{RLD}}}}_F \mathcal{B}   \subset \mathcal{A} \ltimes \mathcal{B} $ for some filter objects $ \mathcal{A} $, $ \mathcal{B} $.

Keywords: filter products

Acyclic list colouring of planar graphs. ★★★

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

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let $ R(k,k) $ denote the $ k^{th} $ diagonal Ramsey number.

Conjecture   $ \lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}} $ exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

Chords of longest cycles ★★★

Author(s): Thomassen

Conjecture   If $ G $ is a 3-connected graph, every longest cycle in $ G $ has a chord.

Keywords: chord; connectivity; cycle

Olson's Conjecture ★★

Author(s): Olson

Conjecture   If $ a_1,a_2,\ldots,a_{2n-1} $ is a sequence of elements from a multiplicative group of order $ n $, then there exist $ 1 \le j_1 < j_2 \ldots < j_n \le 2n-1 $ so that $ \prod_{i=1}^n a_{j_i} = 1 $.

Keywords: zero sum

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If $ G $ is a bridgeless cubic graph, then there exist 6 perfect matchings $ M_1,\ldots,M_6 $ of $ G $ with the property that every edge of $ G $ is contained in exactly two of $ M_1,\ldots,M_6 $.

Keywords: cubic; perfect matching

Laplacian Degrees of a Graph ★★

Author(s): Guo

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

Keywords: degree sequence; Laplacian matrix

Graph product of multifuncoids ★★

Author(s): Porton

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

Keywords: graph-product; multifuncoid

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let $ r \ge 2 $ be an integer and let $ H $ be a minor minimal clutter with $ \frac{1}{r}\tau_r(H) < \tau(H) $. Then either $ H $ has a $ J_k $ minor for some $ k \ge 2 $ or $ H $ has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

Inequality of the means ★★★

Author(s):

Question   Is is possible to pack $ n^n $ rectangular $ n $-dimensional boxes each of which has side lengths $ a_1,a_2,\ldots,a_n $ inside an $ n $-dimensional cube with side length $ a_1 + a_2 + \ldots a_n $?

Keywords: arithmetic mean; geometric mean; Inequality; packing

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted $ {\mathcal O} $, is the graph with vertex set $ {\mathbb R}^2 $ and two points adjacent if the distance between them is an odd integer.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

$C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

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

Keywords: diffeomorphisms,; dynamical systems

Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

Conjecture   $ f \sqcap \bigsqcup S = \bigsqcup \langle f \sqcap \rangle^{\ast} S $ for principal funcoid $ f $ and a set $ S $ of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid