Recent Activity

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

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

Conjecture   If $ G $ is a simple loopless triangulation of an orientable surface, then the dual of $ G $ is 3-edge-colorable.

Keywords: coloring; surface

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational $ \epsilon > 0 $ and every rational $ \Delta $, there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $ I $ on $ n $ variables, for some $ n $, and $ m = \floor{\Delta n} $ clauses drawn uniformly at random from the set of formulas on $ n $ variables. Return with probability at least 0.5 (over the instances) that $ I $ is typical without returning typical for any instance with at least $ (1 - \epsilon)m $ simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

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

Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of $ C_7 $?

Keywords:

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $ S $ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $ S $ has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

Conjecture   Every arrangement graph of a set of great circles is $ 3 $-colourable.

Keywords: arrangement graph; graph coloring

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

Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number $ g(a_1, a_2, \dots, a_n) $ of co-prime positive integers $ a_1, a_2, \dots, a_n $ for $ n\geq 4 $.

Keywords:

Magic square of squares ★★

Author(s): LaBar

Question   Does there exist a $ 3\times 3 $ magic square composed of distinct perfect squares?

Keywords:

Diophantine quintuple conjecture ★★

Author(s):

Definition   A set of m positive integers $ \{a_1, a_2, \dots, a_m\} $ is called a Diophantine $ m $-tuple if $ a_i\cdot a_j + 1 $ is a perfect square for all $ 1 \leq i < j \leq m $.
Conjecture  (1)   Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture  (2)   If $ \{a, b, c, d\} $ is a Diophantine quadruple and $ d > \max \{a, b, c\} $, then $ d = a + b + c + 2bc + 2\sqrt{(ab+1)(ac+1)(bc+1)}. $

Keywords:

Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of $ \mathbb Q $.

Keywords:

Seymour's r-graph conjecture ★★★

Author(s): Seymour

An $ r $-graph is an $ r $-regular graph $ G $ with the property that $ |\delta(X)| \ge r $ for every $ X \subseteq V(G) $ with odd size.

Conjecture   $ \chi'(G) \le r+1 $ for every $ r $-graph $ G $.

Keywords: edge-coloring; r-graph

Edge list coloring conjecture ★★★

Author(s):

Conjecture   Let $ G $ be a loopless multigraph. Then the edge chromatic number of $ G $ equals the list edge chromatic number of $ G $.

Keywords:

Middle levels problem ★★

Author(s): Erdos

Conjecture   Let $ G_n $ be the bipartite graph whose vertices are the $ n $-subsets and the $ (n+1) $-subsets of a $ (2n+1) $-element set, and with inclusion as the adjacency relationship. Then $ G_n $ is Hamiltonian.

Keywords:

Kneser–Poulsen conjecture ★★★

Author(s): Kneser; Poulsen

Conjecture   If a finite set of unit balls in $ \mathbb{R}^n $ is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.

Keywords: pushing disks

Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the $ n $-cube into $ n $-simplices?

Keywords: cube; decomposition; simplex

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

The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle cr(K_n) =   \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $

Keywords: complete graph; crossing number