Open-problem statements, with their sources attached.

Every tree admits a graceful labeling.

A graceful labeling of a tree $T$ with $m$ edges is an injective map $f : V \to \{0, \dots, m\}$ such that the multiset of absolute differences $|f(u) - f(v)|$ over edges $\{u,v\}$ of $T$ equals $\{1, \dots, m\}$.

The Komlós conjecture*

There exists a universal constant $K > 0$ such that for all $n, m \in \mathbb{N}$ and all vectors $v_1, \dots, v_n \in \mathbb{R}^m$ with $\|v_i\|_2 \le 1$ (encoded here as $\sum_j v_{ij}^2 \le 1$), there exist signs $\varepsilon_i \in \{-1, +1\}$ such that $\left\|\sum_i \varepsilon_i v_i\right\|_\infty \le K$, i.e. $\left|\sum_i \varepsilon_i v_{ij}\right| \le K$ for every coordinate $j$.

Does there exist a $3 \times 3$ semi-magic square whose entries are all distinct positive integer cubes? A square is semi-magic if all rows and columns sum to the same total.

More precisely, we seek a $3 \times 3$ matrix with entries $a_{ij}$ such that each $a_{ij} = n_{ij}^3$ for some positive integer $n_{ij}$, all nine cubes are distinct, and all row sums and column sums are equal. Reference:* Semi-Magic Square of Cubes

The pebbling number conjecture: the pebbling number of a Cartesian product of connected graphs is at most equal to the product of the pebbling numbers of the factors. See Asplund, Hurlbert, and Kenter.

The open problem: determine the Ramsey number $R(5,5)$.

It is known that $43 \le R(5,5) \le 46$.

Sidorenko's conjecture (1993).*

For every finite bipartite simple graph $H$ and every finite simple graph $G$: $t(H, G) \ge t(K_2, G)^{e(H)}$, where $K_2$ denotes the single-edge graph on 2 vertices (i.e. completeGraph (Fin 2)).

For dimension $9$, the length of the longest snake in the box is not known. This is currently the smallest dimension where this question is open.

Wichmann's conjecture on optimal rulers.* Every optimal ruler with more than $13$ segments is a Wichmann ruler $W(r, s)$ (up to reflection, i.e. reversing the segment list). Posed by Wichmann [Wi63]; the finitely many known exceptions all have at most $13$ segments (lengths $1, 13, 17, 23, 58$), and no further exceptions are known up to length $213$.

Construct an $S(t, k, n)$-Steiner system with $n > k > t > 5$, $t < 10$, and $n < 200$.

No example of a Steiner system with $t > 5$ is known, despite a 2014 existence theorem by Keevash showing that such systems must exist for sufficiently large $n$. Reference:* Large Steiner Systems

For every finite union-closed family of sets, other than the family containing only the empty set, there exists an element that belongs to at least half of the sets in the family.

If the UC conjecture is tight for some family A then $|A| = 2^k$ for some $k$.

Reference: Conjecture 3 in https://www.nieuwarchief.nl/serie5/pdf/naw5-2023-24-4-225.pdf.

WOWII Conjecture 100 (status O):

For a simple connected graph G, α(G) ≤ ⌈(max_v l(v) + 0.5 · diam(Gᶜ)) / 2⌉ where α(G) = G.indepNum is the independence number, max_v l(v) is the maximum over all vertices of the independence number of the neighbourhood (in G), and diam(Gᶜ) is the diameter of the complement Gᶜ. Note:* length(Ḡ) in DeLaVina's original is interpreted here as the diameter of the complement. The hypothesis hGc : Gᶜ.Connected is added so that diam(Gᶜ) is finite (otherwise Gᶜ.ediam = ⊤ and Gᶜ.ediam.toNat collapses silently to 0); see the module docstring above.

WOWII Conjecture 133:

For a simple connected graph $G$, $\operatorname{path}(G) \ge \operatorname{rad}(G) + \lfloor \mathrm{avg}_v\, l(v) \rfloor^{cC_4(G)}$, where $\operatorname{path}(G)$ is the path number of the graph (number of vertices of a largest induced path), $\operatorname{rad}(G)$ is the radius (minimum eccentricity, as a natural number), $\mathrm{avg}_v\, l(v) = l(G)$ is the average independence number of vertex neighbourhoods, and $cC_4(G)$ is the $C_4$-free characteristic function (1 if $G$ is $C_4$-free, not necessarily induced, and 0 otherwise).

We read DeLaVina's bracket notation [average of λ(v)] in the source as the floor (a standard Graffiti.pc convention), hence ⌊l G⌋ in Lean.

WOWII Conjecture 141

For a simple connected graph G, tree(G) ≥ ⌊girth(G) / 2⌋ - 1 + max_v l(v) where tree(G) is the number of vertices of a largest induced tree subgraph, girth(G) is the length of the shortest cycle (0 if acyclic), and l(v) = indepNeighbors G v is the independence number of the neighbourhood of v.

WOWII Conjecture 142:

For a simple connected graph $G$, $\mathrm{tree}(G) \ge (2/3) \cdot \mathrm{girth}(G) + \mathrm{ecc}(B)$ where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle ($0$ if acyclic), $B$ is the set of boundary vertices (those of maximum eccentricity), and $\mathrm{ecc}(B)$ is the eccentricity of the set $B$.

WOWII Conjecture 144

For a simple connected graph $G$, $\mathrm{tree}(G) \ge \mathrm{girth}(G) - 1 + \mathrm{ecc}(\mathrm{Centers})$ where $\mathrm{tree}(G)$ is the largest induced tree size, $\mathrm{girth}(G)$ is the length of the shortest cycle ($0$ if acyclic), $\mathrm{Centers} = G.\mathrm{center}$ is the set of vertices with minimum eccentricity (the center of $G$), and $\mathrm{ecc}(\mathrm{Centers})$ is the eccentricity of the center set , the maximum distance from any non-center vertex to the nearest center vertex.

WOWII Conjecture 145

For a simple connected graph $G$, $\mathrm{tree}(G) \ge 2 \cdot \mathrm{ecc}(B) / \lambda_{\min}(\overline{G})$ where $\mathrm{tree}(G)$ is the number of vertices in a largest induced subtree, $\mathrm{ecc}(B)$ is the eccentricity of the boundary vertices (eccSet and boundaryVertices), and $\lambda_{\min}(\overline{G})$ is the minimum local independence number of the complement graph.

We state the inequality in the form $\mathrm{tree}(G) \cdot \mathrm{lMin}(\overline{G}) \ge 2 \cdot \mathrm{ecc}(B)$ to avoid division.

WOWII Conjecture 146

For a simple connected graph $G$, $\mathrm{tree}(G) \ge 2 \cdot \mathrm{ecc}(B) / \mathrm{rad}(G^2)$ where $\mathrm{tree}(G)$ is the number of vertices in a largest induced subtree, $\mathrm{ecc}(B)$ is the eccentricity of the boundary vertices of $G$ (eccSet and maxEccentricityVertices), and $\mathrm{rad}(G^2)$ is the radius of the square graph of $G$.

We state the inequality in the form $\mathrm{tree}(G) \cdot \mathrm{rad}(G^2) \ge 2 \cdot \mathrm{ecc}(B)$ to avoid division.

WOWII Conjecture 160

For a simple connected graph $G$, $L_s(G) \ge \max_v l(v) + \max_v T(v) \cdot c_{C_4}(G)$ where:

• $L_s(G) = \mathrm{SimpleGraph.Ls}\, G$ is the maximum number of leaves over all spanning trees of $G$,
• $\max_v l(v)$ is the maximum local independence number over vertices,
• $\max_v T(v)$ is the maximum number of triangles incident to any vertex,
• $c_{C_4}(G)$ is the number of induced 4-cycles in $G$.

WOWII Conjecture 19

If G is connected then the size b(G) of a largest induced bipartite subgraph satisfies b(G) ≥ FLOOR((∑ ecc(v))/(|V|) + sSup (range (l G))), where ecc(v) denotes eccentricity and l(G) is the independence number of neighbourhoods.