Open-problem statements, with their sources attached.

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.

WOWII Conjecture 194

For a simple connected graph G, if α(G) ≤ 1 + l_avg(G), then G has a Hamiltonian path. Here α(G) = G.indepNum is the independence number, and l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number of the neighbourhood. A Hamiltonian path is a walk visiting every vertex exactly once.

WOWII Conjecture 198a

For a simple connected graph G, if b(G) ≤ 2 + ecc_avg(G), then G has a Hamiltonian path. Here b(G) is the number of vertices in a largest induced bipartite subgraph, and ecc_avg(G) is the average eccentricity of G. A Hamiltonian path is a walk visiting every vertex exactly once.