Size Ramsey numbers of hypergraphs

DefinitionHypergraph arrowing the complete 3-uniform hypergraph#✓fully proved

Let \(H\) be a family of subsets of \(\{0, \dots, N-1\}\) and let \(n\) be a natural number. Then \(H\) arrows \(K_n^{(3)}\) when for every colouring of the subsets of \(\{0, \dots, N-1\}\) with two colours there exist an \(n\)-element set \(S \subseteq \{0, \dots, N-1\}\) and a colour such that every 3-element subset of \(S\) belongs to \(H\) and has that colour.

def Arrows3 {N : ℕ} (H : Finset (Finset (Fin N))) (n : ℕ) : Prop :=
  ∀ c : Finset (Fin N) → Bool, ∃ S : Finset (Fin N), S.card = n ∧
    ∃ col : Bool, ∀ f ⊆ S, f.card = 3 → f ∈ H ∧ c f = col

Used by 1

Used by3-uniform size Ramsey number

DefinitionDiagonal 3-uniform Ramsey number#✓fully proved

For a natural number \(n\), the Ramsey number \(r_3(n, n)\) is the least natural number \(N\) such that for every colouring of the subsets of \(\{0, \dots, N-1\}\) with two colours there is an \(n\)-element set \(S \subseteq \{0, \dots, N-1\}\) all of whose 3-element subsets have the same colour.

noncomputable def ramsey3 (n : ℕ) : ℕ :=
  sInf {N | ∀ c : Finset (Fin N) → Bool, ∃ S : Finset (Fin N), S.card = n ∧
    ∃ col : Bool, ∀ f ⊆ S, f.card = 3 → c f = col}

Used by 1

Used byDudek–Rödl size Ramsey question

Definition3-uniform size Ramsey number#✓fully proved

For a natural number \(n\), the size Ramsey number \(\hat r_3(n, n)\) is the least natural number \(m\) such that for some \(N\) there is a 3-uniform hypergraph \(H\) on \(\{0, \dots, N-1\}\) with exactly \(m\) edges that arrows \(K_n^{(3)}\).

noncomputable def sizeRamsey3 (n : ℕ) : ℕ :=
  sInf {m | ∃ (N : ℕ) (H : Finset (Finset (Fin N))), (∀ e ∈ H, e.card = 3) ∧ H.card = m ∧
    Arrows3 H n}

Uses 1 · Used by 1

Statement usesHypergraph arrowing the complete 3-uniform hypergraph

Used byDudek–Rödl size Ramsey question

DefinitionDudek–Rödl size Ramsey question#✓fully proved

The statement that for every natural number \(n\) the 3-uniform size Ramsey number \(\hat r_3(n, n)\) equals the binomial coefficient \(\binom{r_3(n, n)}{3}\), where \(r_3(n, n)\) is the diagonal 3-uniform Ramsey number (AimPL Graph Ramsey Theory, Problem 1.08).

def sizeRamseyEqualsBinomial : Prop :=
  ∀ n : ℕ, sizeRamsey3 n = (ramsey3 n).choose 3

Uses 2 · Used by 1

Statement usesDiagonal 3-uniform Ramsey number · 3-uniform size Ramsey number

Used byThe Dudek–Rödl size Ramsey question has a negative answer

TheoremThe Dudek–Rödl size Ramsey question has a negative answer#●ready to prove

It is not true that for every natural number \(n\) the 3-uniform size Ramsey number \(\hat r_3(n, n)\) equals the binomial coefficient \(\binom{r_3(n, n)}{3}\), where \(r_3(n, n)\) is the diagonal 3-uniform Ramsey number.

McKay shows that the complete 3-uniform hypergraph \(K_{13}^{(3)}\) on 13 vertices with one triple removed cannot be 2-coloured without a monochromatic copy of the complete 3-uniform hypergraph \(K_4^{(3)}\) on 4 vertices; since \(r_3(4, 4) = 13\) (McKay and Radziszowski, 1991, recalled in the same paper) this gives \(\hat r_3(4, 4) \le 285 < 286 = \binom{13}{3}\), "which answers Dudek et al.'s question in the negative".

public theorem_wanted sizeRamseyEqualsBinomial_refuted : ¬ sizeRamseyEqualsBinomial

Sources

• AimPL: Graph Ramsey Theory, Problem 1.08 [Andrzej Dudek] (Dudek–Rödl), http://aimpl.org/graphramsey/1/ (Question 2.2 of Dudek, La Fleur, Mubayi and Rödl, J. Graph Theory 86 (2017)); resolution: B. D. McKay, A class of Ramsey-extremal hypergraphs, Trans. Comb. 6 (2017), no. 3, 37-43, arXiv:1608.07762, abstract and Section 3 (last paragraph), https://toc.ui.ac.ir/article_21468.html.

Uses 1

Statement usesDudek–Rödl size Ramsey question

4 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.