Open Problem Garden

staroid

Multicolour Erdős--Hajnal Conjecture ★★★

Conjecture For every fixed $k\geq2$ and fixed colouring $\chi$ of $E(K_k)$ with $m$ colours, there exists $\varepsilon>0$ such that every colouring of the edges of $K_n$ contains either $k$ vertices whose edges are coloured according to $\chi$ or $n^\varepsilon$ vertices whose edges are coloured with at most $m-1$ colours.

Keywords: ramsey theory

Posted by Jon Noel
updated October 10th, 2019

add new comment

density problems

Graph Theory

Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture For any bipartite graph $H$ and graph $G$ , the number of homomorphisms from $H$ to $G$ is at least $\left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|}$ .

Keywords: density problems; extremal combinatorics; homomorphism

Posted by Jon Noel
updated October 10th, 2019

add new comment

Sidorenko, A.

Geometry

Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

Posted by Erik Demaine
updated June 18th, 2019

add new comment

nets

Pascal's triangle

Number Theory » Combinatorial N.T.

Singmaster's conjecture ★★

Author(s): Singmaster

Conjecture There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number $1$ .

The number $2$ appears once in Pascal's triangle, $3$ appears twice, $6$ appears three times, and $10$ appears $4$ times. There are infinite families of numbers known to appear $6$ times. The only number known to appear $8$ times is $3003$ . It is not known whether any number appears more than $8$ times. The conjectured upper bound could be $8$ ; Singmaster thought it might be $10$ or $12$ . See Singmaster's conjecture.