Open Problem Garden

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

Posted by Jon Noel
updated September 20th, 2015

add new comment

Combinatorics

Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

Question What is the saturation number of cycles of length $2\ell$ in the $d$ -dimensional hypercube?

Keywords: cycles; hypercube; minimum saturation; saturation

Posted by Jon Noel
updated September 20th, 2015

add new comment

Graph Theory » Coloring » Vertex coloring

Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

Conjecture If $\chi(G)>k$ , then $G$ contains at least $\frac{(k+1)(k-1)!}{2}$ cycles of length $0\bmod k$ .

Keywords: chromatic number; cycles

Posted by Jon Noel
updated September 20th, 2015

add new comment

Combinatorics

The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture The largest measure of a Lebesgue measurable subset of the unit sphere of $\mathbb{R}^n$ containing no pair of orthogonal vectors is attained by two open caps of geodesic radius $\pi/4$ around the north and south poles.

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

Posted by Jon Noel
updated September 15th, 2015

add new comment

flow conjectures

Graph Theory

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