Transversal-critical triple systems

DefinitionErdős Problem 834 for transversal-critical triple systems#✓fully proved

There exist \(n \in \mathbb{N}\) and a \(3\)-uniform hypergraph \(H\) on the vertex set \(\{0, \dots, n-1\}\) such that some set of at most \(3\) vertices meets every edge of \(H\), no set of at most \(2\) vertices meets every edge of \(H\), for every edge \(e\) of \(H\) some set of at most \(2\) vertices meets every edge of \(H\) other than \(e\), and every vertex lies in at least \(7\) edges of \(H\).

Writing \(\tau\) for the least size of a vertex set meeting every edge and \(H - e\) for \(H\) with the edge \(e\) removed, this asks for \(\tau(H) = 3\) and \(\tau(H - e) \le 2\) for every edge \(e\), with every vertex of degree at least \(7\).

def transversalCriticalMinDegreeSeven : Prop :=
  ∃ (n : ℕ) (H : Finset (Finset (Fin n))), SetFamily.IsUniform H 3 ∧
    (∃ T : Finset (Fin n), T.card ≤ 3 ∧ ∀ f ∈ H, (f ∩ T).Nonempty) ∧
    (¬ ∃ T : Finset (Fin n), T.card ≤ 2 ∧ ∀ f ∈ H, (f ∩ T).Nonempty) ∧
    (∀ e ∈ H, ∃ T : Finset (Fin n), T.card ≤ 2 ∧ ∀ f ∈ H.erase e, (f ∩ T).Nonempty) ∧
    ∀ v : Fin n, 7 ≤ (H.filter (v ∈ ·)).card

Uses 1 · Used by 1

Statement usesUniform hypergraphs

Used byErdős Problem 834 fails for transversal-critical triple systems

TheoremErdős Problem 834 fails for transversal-critical triple systems#●ready to prove

There are no \(n \in \mathbb{N}\) and \(3\)-uniform hypergraph \(H\) on the vertex set \(\{0, \dots, n-1\}\) such that some set of at most \(3\) vertices meets every edge of \(H\), no set of at most \(2\) vertices meets every edge of \(H\), for every edge \(e\) of \(H\) some set of at most \(2\) vertices meets every edge of \(H\) other than \(e\), and every vertex lies in at least \(7\) edges of \(H\).

Writing \(\tau(H)\) for the least size of a vertex set meeting every edge of \(H\) and \(H - e\) for \(H\) with the edge \(e\) removed, Li proved that a \(3\)-uniform hypergraph \(H\) with \(\tau(H) = 3\) and \(\tau(H - e) = 2\) for every edge \(e\) has at most \(10\) edges, so some vertex has degree at most \(6\).

public theorem_wanted transversalCriticalMinDegreeSeven_refuted :
    ¬ transversalCriticalMinDegreeSeven

Sources

• T. F. Bloom, Erdős Problems, Problem #834, https://www.erdosproblems.com/834 (status SOLVED); resolution: R. Li, On an Erdős-Lovász problem: 3-critical 3-graphs of minimum degree 7, arXiv:2512.24850 (2025; unrefereed, accepted on erdosproblems.com/834), abstract and main theorem for the transversal interpretation: a 3-uniform hypergraph H with τ(H) = 3 and τ(H - e) = 2 for every edge e has at most 10 edges, in particular δ(H) ≤ 6, sharp for K₅⁽³⁾; erdosproblems.com/834: 'In the first formulation ... Li proves that a 3-critical 3-uniform hypergraph must have a vertex of degree ≤ 6', https://arxiv.org/abs/2512.24850.

Uses 1

Statement usesErdős Problem 834 for transversal-critical triple systems

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.