Random

Barnette's Conjecture ★★★

Author(s): Barnette

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

Keywords: bipartite; cubic; hamiltonian

trace inequality ★★

Author(s):

Let $ A,B $ be positive semidefinite, by Jensen's inequality, it is easy to see $ [tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}} $, whenever $ s>r>0 $.

What about the $ tr(A^s+B^s)^{\frac{1}{s}}\leq tr(A^r+B^r)^{\frac{1}{r}} $, is it still valid?

Keywords:

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

Order-invariant queries ★★

Author(s): Segoufin

Question  
    \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} $?

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

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

Conjecture   Every graph with average degree at least $ \frac{4}{3}t-2 $ contains every 2-regular graph on $ t $ vertices as a minor.

Keywords: minors

Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★

Author(s):

Conjecture   Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

Keywords: 2-error-correcting; code; existence; perfect; perfect code

Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is $ k $-diregular if every vertex has indegree and outdegree at least $ k $.

Conjecture   For $ d >2 $, every $ d $-diregular oriented graph on at most $ 4d+1 $ vertices has a Hamilton cycle.

Keywords:

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $ G $, let $ s(G) $ ($ s'(G) $) denote the smallest integer $ m $ so that every sequence of $ m $ elements of $ G $ has a subsequence of length $ >0 $ (length $ |G| $) which has product equal to 1 in some order.

Conjecture   $ s'(G) = s(G) + |G| - 1 $ for every finite group $ G $.

Keywords: subsequence sum; zero sum

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

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

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The average diameter of a bounded cell of a simple arrangement defined by $ n $ hyperplanes in dimension $ d $ is not greater than $ d $.

Keywords: arrangement; diameter; polytope

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

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

Keywords: Inequality; Probability Theory; randomness in TCS

Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-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 $.

Question   Does there exist a fixed constant $ c $ so that every convex 4-polytope has fatness at most $ c $?

Keywords: f-vector; polytope

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $ G $ be a finite undirected simple graph.

A $ k $-page book embedding of $ G $ consists of a linear order $ \preceq $ of $ V(G) $ and a (non-proper) $ k $-colouring of $ E(G) $ such that edges with the same colour do not cross with respect to $ \preceq $. That is, if $ v\prec x\prec w\prec y $ for some edges $ vw,xy\in E(G) $, then $ vw $ and $ xy $ receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of $ G $, denoted by bt$ (G) $ is the minimum integer $ k $ for which there is a $ k $-page book embedding of $ G $.

Let $ G' $ be the graph obtained by subdividing each edge of $ G $ exactly once.

Conjecture   There is a function $ f $ such that for every graph $ G $, $$   \text{bt}(G) \leq f( \text{bt}(G') )\enspace.   $$

Keywords: book embedding; book thickness

A gold-grabbing game ★★

Author(s): Rosenfeld

Setup Fix a tree $ T $ and for every vertex $ v \in V(T) $ a non-negative integer $ g(v) $ which we think of as the amount of gold at $ v $.

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex $ v $ of the tree, takes the gold at this vertex, and then deletes $ v $. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

Problem   Find optimal strategies for the players.

Keywords: game; tree

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:

Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

Conjecture   Every even number greater than $ 10 $ can be represented as the sum of an odd prime number and an odd semiprime .

Keywords: prime; semiprime

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

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

Here $ G \times H $ is the tensor product (also called the direct or categorical product) of $ G $ and $ H $.

Keywords: categorical product; coloring; homomorphism; tensor product

Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a $ K_6 $ minor is apex (planar plus one vertex).

Keywords: connectivity; minor

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

Exact colorings of graphs ★★

Author(s): Erickson

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: graph coloring; ramsey theory

Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index $ \chi_s'(G) $ of a graph $ G $ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph $ G $, we have $ \chi_s'(G) \le 6 $?

Keywords: edge coloring; star coloring

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

Author(s):

Conjecture  

There exists a finite lattice that is not an interval in the subgroup lattice of a finite group.

Keywords: congruence lattice; finite groups

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

Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture   Let $ f\in Diff^{r}(M) $ and $ p\in\omega_{f}  $. Then for any neighborhood $ V_{f}\subset Diff^{r}(M)  $ there is $ g\in V_{f} $ such that $ p $ is periodic point of $ g $

There is an analogous conjecture for flows ( $ C^{r} $ vector fields . In the case of diffeos this was proved by Charles Pugh for $ r = 1 $. In the case of Flows this has been solved by Sushei Hayahshy for $ r = 1 $ . But in the two cases the problem is wide open for $ r > 1 $

Keywords: Dynamics , Pertubation

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture   For every prime $ p $, there is a constant $ c(p) $ (possibly $ c(p)=p $) so that the union (as multisets) of any $ c(p) $ bases of the vector space $ ({\mathbb Z}_p)^n $ contains an additive basis.

Keywords: additive basis; matrix

Mixing Circular Colourings

Author(s): Brewster; Noel

Question   Is $ \mathfrak{M}_c(G) $ always rational?

Keywords: discrete homotopy; graph colourings; mixing

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

The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let $ f(n) = 3n+1 $ if $ n $ is odd and $ \frac{n}{2} $ if $ n $ is even. Let $ f(1) = 1 $. Assume we start with some number $ n $ and repeatedly take the $ f $ of the current number. Prove that no matter what the initial number is we eventually reach $ 1 $.

Keywords: integer sequence

Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued funcoid is monovalued.

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let $ G $ be an abelian group of odd order and let $ A,B \subseteq G $ satisfy $ |A| = |B| = k $. Then the elements of $ A $ and $ B $ may be ordered $ A = \{a_1,\ldots,a_k\} $ and $ B = \{b_1,\ldots,b_k\} $ so that the sums $ a_1+b_1, a_2+b_2 \ldots, a_k + b_k $ are pairwise distinct.

Keywords: addition table; latin square; transversal

Euler-Mascheroni constant ★★★

Author(s):

Question   Is Euler-Mascheroni constant an transcendental number?

Keywords: constant; Euler; irrational; Mascheroni; rational; transcendental

Switching reconstruction conjecture ★★

Author(s): Stanley

Conjecture   Every simple graph on five or more vertices is switching-reconstructible.

Keywords: reconstruction

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

Lucas Numbers Modulo m ★★

Author(s):

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.

Keywords: Lucas numbers

A conjecture about direct product of funcoids ★★

Author(s): Porton

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

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

Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

Conjecture   Every bidirected graph with a nowhere-zero $ k $-flow for some $ k $, has a nowhere-zero $ 6 $-flow.

Keywords: bidirected graph; nowhere-zero flow

Point sets with no empty pentagon

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

Nonseparating planar continuum ★★

Author(s):

Conjecture   Does any path-connected, compact set in the plane which does not separate the plane have the fixed point property?

A set has the fixed point property if every continuous map from it into itself has a fixed point.

Keywords: fixed point

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

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

Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $ c $ of colours to the vertices such that no two arcs receive ordered pairs of colours $ (c_1,c_2) $ and $ (c_2,c_1) $. It is equivalent to a homomorphism of the digraph onto some tournament of order $ k $.

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

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

Are all Mersenne Numbers with prime exponent square-free? ★★★

Author(s):

Conjecture   Are all Mersenne Numbers with prime exponent $ {2^p-1} $ Square free?

Keywords: Mersenne number

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers $ k,n \ge 2 $, the 2-stage Shuffle-Exchange graph/network, denoted $ \text{SE}(k,n) $, is the simple $ k $-regular bipartite graph with the ordered pair $ (U,V) $ of linearly labeled parts $ U:=\{u_0,\dots,u_{t-1}\} $ and $ V:=\{v_0,\dots,v_{t-1}\} $, where $ t:=k^{n-1} $, such that vertices $ u_i $ and $ v_j $ are adjacent if and only if $ (j - ki) \text{ mod } t < k $ (see Fig.1).

Given integers $ k,n,r \ge 2 $, the $ r $-stage Shuffle-Exchange graph/network, denoted $ (\text{SE}(k,n))^{r-1} $, is the proper (i.e., respecting all the orders) concatenation of $ r-1 $ identical copies of $ \text{SE}(k,n) $ (see Fig.1).

Let $ r(k,n) $ be the smallest integer $ r\ge 2 $ such that the graph $ (\text{SE}(k,n))^{r-1} $ is rearrangeable.

Problem   Find $ r(k,n) $.
Conjecture   $ r(k,n)=2n-1 $.

Keywords:

Convex 'Fair' Partitions Of Convex Polygons ★★

Author(s): Nandakumar; Ramana

Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?

Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.

Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?

2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?

3. Finally, what could one say about higher dimensional analogs of this question?

Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n

Keywords: Convex Polygons; Partitioning

Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem   Does every $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?

Keywords:

List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture   Suppose that $ G $ is a $ \Delta $-edge-critical graph. Suppose that for each edge $ e $ of $ G $, there is a list $ L(e) $ of $ \Delta $ colors. Then $ G $ is $ L $-edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring