Chapter 20: Hypergraph Theory

Why does forbidding a triple behave differently from forbidding an edge?

Suppose three operations can safely run in any pair, but running all three together exhausts a shared resource. A graph of pairwise incompatibilities cannot express this rule faithfully: forbidding any pair rejects a safe combination, while allowing all three pairs misses the joint conflict. A hypergraph records the entire forbidden triple as one object.

A hypergraph is a pair $H=(V,E)$, where $V$ is a finite vertex set and $E$ is a family of distinct nonempty subsets of $V$, called hyperedges. We use simple hypergraphs: no repeated hyperedges. A graph is the special case in which every hyperedge has size two. The meaning of a hyperedge depends on the application: it can represent a joint conflict, a collaboration, a simultaneous requirement, or a forbidden configuration.

Many graph definitions extend naturally, but their theorems need not. A matching still consists of disjoint edges; a cover still meets every edge. Yet the matching-cover equality for bipartite graphs fails in general hypergraphs. Coloring also changes: avoiding a monochromatic triple does not require its three vertices to receive three different colors.

The chapter's goal is to define these objects precisely, solve several small instances, and identify which familiar graph arguments survive and which need information about higher-order intersections.

20.1 Hypergraph fundamentals, rank, and uniformity

The order of $H$ is $|V|$, and its size is $|E|$. Its rank is $\max_{e\in E}|e|$, with rank zero for an empty edge family. It is $r$-uniform if every edge has exactly $r$ vertices; the notation $r$-graph is often used for this case. An $r$-uniform hypergraph is therefore a set family $E\subseteq\binom Vr$, directly connecting this chapter to extremal set theory.

The degree $d_H(v)$ counts edges containing $v$. More generally, for a vertex subset $S$, its codegree is

$$ d_H(S)=|\{e\in E:S\subseteq e\}|. $$

For a 3-graph, a vertex degree counts triples through that vertex, while a pair codegree counts possible third vertices. These are different levels of information.

Solved example. Let $V=[6]$ and $E=\{12,234,1456\}$. The rank is 4, but the hypergraph is not uniform. Its degree sequence in vertex order is $(2,2,1,2,1,1)$, and

$$ \sum_{v\in V}d_H(v)=9=2+3+4=\sum_{e\in E}|e|. $$

This identity double-counts vertex-edge incidences. For an $r$-uniform hypergraph with $m$ edges it becomes $\sum_v d_H(v)=rm$.

The incidence graph is bipartite: one side represents vertices, the other represents hyperedges, and an incidence edge joins $v$ to $e$ exactly when $v\in e$. Unlike the pair shadow, the full incidence graph retains edge identities and membership. But a matching in this bipartite incidence graph selects distinct representatives for distinct hyperedges; it does not require those hyperedges to be disjoint. For example, 123 and 145 can receive representatives 2 and 4 while still intersecting at 1.

For an $r$-graph, the link of $v$ is the $(r-1)$-graph on $V\setminus\{v\}$ whose edges are $e\setminus\{v\}$ for edges $e$ containing $v$. In a 3-graph, each link is an ordinary graph. Links expose local structure, while shadows aggregate over several possible centers.

Exercise. For the 3-graph with edges 123, 124, and 145, list the link of vertex 1 and compute $d_H(\{1,2\})$. Hint: remove 1 from every edge through it. Solution: the link edges are 23, 24, and 45; the pair codegree is 2.

20.2 Hypergraph matching and covering

A matching is a family of pairwise disjoint hyperedges; its maximum size is $\nu(H)$. A vertex cover, also called a transversal, is a set $T\subseteq V$ meeting every edge; its minimum size is $\tau(H)$. An independent set contains no entire edge. Complements interchange independent sets and covers, giving

$$ \alpha(H)+\tau(H)=|V(H)|, $$

where $\alpha(H)$ is the largest independent-set size.

Every cover must use a different vertex for each edge of a matching, so $\nu(H)\le\tau(H)$. For rank at most $r$,

$$ \nu(H)\le\tau(H)\le r\nu(H). $$

Proof of the upper bound. Choose any maximal matching $M$: no further edge can be added while preserving disjointness. Its vertex union meets every edge, or an edge avoiding the union could be added. That union has at most $r|M|\le r\nu(H)$ vertices and is a cover. A maximal matching is not necessarily a maximum matching; the proof uses only the fact that a maximum is at least as large.

This also gives a factor-$r$ guarantee for a greedy maximal matching. A maximum matching has at most $r|M|$ edges, because its disjoint edges each meet the union of $M$, and each vertex in that union can meet at most one of them.

Solved example of failure of equality. Consider the seven triples

$$ \mathcal F=\{123,145,167,246,257,347,356\} $$

on $[7]$, the Fano plane. Every pair of distinct edges meets in exactly one vertex, so $\nu=1$. Each vertex lies in three edges, and each pair of vertices lies in exactly one edge. Two vertices therefore cover exactly $3+3-1=5$ of the seven edges, so $\tau\ge3$. The edge 123 meets every edge and is a three-vertex cover, proving $\tau=3$. Thus the rank-3 inequality is tight, and the bipartite graph matching-cover equality cannot be transferred without further assumptions.

Exercise. For all triples containing vertex 1 on $[6]$, find $\nu$, $\tau$, and $\alpha$. Hint: every edge shares its center. Solution: $\nu=\tau=1$, and $\alpha=5$, witnessed by the other five vertices.

20.3 Hypergraph coloring and property B

A weak proper coloring assigns colors to vertices so that no edge is monochromatic. Its minimum number of colors is $\chi(H)$. Property B means that a weak proper coloring with two colors exists. A strong coloring instead requires every pair of vertices in an edge to have different colors. These coincide for graphs but differ for edges of size three or more.

Solved example. For the four-edge hypergraph in the matching workshop, color $\{1,6\}$ red and the other four vertices blue. Every edge contains one red and two blue vertices, so property B holds. This coloring is weakly proper, but not strongly proper.

A useful sufficient condition follows from a random coloring. If an $r$-uniform hypergraph has $m$ edges, independently color each vertex red or blue with equal probability. A given edge is monochromatic with probability $2^{1-r}$. The union bound gives

$$ \Pr(\text{some monochromatic edge})\le m2^{1-r}. $$

If $m\lt2^{r-1}$, a good coloring exists. This condition is sufficient, not necessary: many larger families are still two-colorable. A singleton edge, however, is monochromatic in every vertex coloring, so edge sizes matter.

Why the Fano plane fails property B. Its seven edges contain every vertex pair exactly once. In a red-blue coloring, let $R,B$ be the two color-class sizes and let $M$ be the number of monochromatic edges. A nonmonochromatic triple contributes one same-color pair, while a monochromatic triple contributes three. Counting same-color pairs through their unique Fano edges gives

$$ \binom R2+\binom B2=7+2M,\qquad R+B=7. $$

The left side is minimized at $R=3,B=4$, where it equals 9. Hence $M\ge1$ in every coloring. This is a complete obstruction proof, not a failed attempt to find a coloring.

The incidence matrix below shows one trial coloring: vertices 1, 2, and 3 are red, and vertices 4 through 7 are teal. A filled dot means the column vertex belongs to the row edge; its color repeats the vertex color. The first row is monochromatic. Each of the other six rows has one red and two teal members. The proof above shows that changing the coloring cannot make every row mixed.

Exercise. Delete the Fano edge 123. Find a valid two-coloring of the remaining six edges. Hint: use the coloring in the SVG. Solution: red $\{1,2,3\}$ and teal $\{4,5,6,7\}$ works, since the only monochromatic row of that trial has been deleted.

20.4 Hypergraph Turán problems

For a fixed $r$-uniform hypergraph $F$ with at least one edge, define

$$ \operatorname{ex}_r(n,F)=\max\{|E(H)|:|V(H)|=n,\ H\text{ is an }F\text{-free }r\text{-graph}\}. $$

A copy uses an injective map of the vertices of $F$ preserving every edge; it need not preserve nonedges. The complete $r$-graph on $t$ vertices, denoted $K_t^{(r)}$, contains all $\binom tr$ possible edges.

Solved example. The tetrahedron $K_4^{(3)}$ consists of the four triples on four vertices. On exactly four vertices, forbidding it allows at most three edges, and any three of the four triples attain that bound. Thus $\operatorname{ex}_3(4,K_4^{(3)})=3$. Both the three-edge construction and the full tetrahedron have pair shadow $K_4$, as the opening card showed.

For $n\ge r$, define edge density by $|E(H)|/\binom nr$. The Turán density is

$$ \pi(F)=\lim_{n\to\infty}\frac{\operatorname{ex}_r(n,F)}{\binom nr}. $$

Why this limit exists. Take an extremal $F$-free $r$-graph on $n$ vertices and choose a uniformly random $m$-vertex subset, with $r\le m\le n$. Its induced hypergraph remains $F$-free, while its expected edge count is

$$ \operatorname{ex}_r(n,F)\frac{\binom mr}{\binom nr}\le\operatorname{ex}_r(m,F). $$

Hence the normalized extremal numbers are nonincreasing and bounded below by zero, so they converge. This elementary averaging fact establishes the density's existence, not its value.

Unlike graph clique problems, uniform hypergraph clique problems do not admit a general exact balanced-partite formula. Section 20.10 constructs a $K_4^{(3)}$-free family of asymptotic density $5/9$, proving a lower bound. It should not be promoted to an optimality theorem merely because it is explicit or looks symmetric.

A case with a matching exact theorem. Let $F$ be two disjoint triples. Being $F$-free is exactly being intersecting. For $n\ge6$, the Erdős–Ko–Rado theorem from Chapter 18 gives

$$ \operatorname{ex}_3(n,F)=\binom{n-1}{2}, $$

attained by all triples containing a fixed vertex. Here the set-family theorem supplies the upper bound missing from a construction alone.

Exercise. Compute the edge count of this intersecting construction on eight vertices. Hint: choose the two noncentral vertices. Solution: $\binom72=21$, and EKR proves that no intersecting family of triples on eight vertices is larger.

20.5 Linear, intersecting, and multipartite hypergraphs

A hypergraph is linear if two distinct edges intersect in at most one vertex. It is intersecting if two distinct edges always meet. A linear intersecting hypergraph therefore has exactly one common vertex for each pair of edges, but it need not have a single vertex common to all edges.

An $r$-partite $r$-graph has a vertex partition $V_1,\ldots,V_r$ and exactly one vertex from each part in every edge. It is complete when every such choice is an edge. If the part sizes are $n_1,\ldots,n_r$, its edge count is $\prod_i n_i$. Equal part sizes maximize this product for a fixed total, up to integer rounding.

Solved comparisons. The Fano plane is linear and intersecting, with no universal vertex. The complete 3-partite 3-graph with part sizes $2,2,2$ has eight edges and a matching of size two. It is not linear: edges 135 and 136, for parts $\{1,2\},\{3,4\},\{5,6\}$, share two vertices. It is not intersecting, since 135 and 246 are disjoint.

The Fano plane cannot be 3-partite: every vertex pair lies together in some edge, which would force all seven vertices into different parts. This contrasts weak two-colorability, strong coloring, and partiteness. A two-coloring with no monochromatic edge is not automatically a partition with at most one vertex of each part per edge.

A counting consequence of linearity. In a linear $r$-uniform hypergraph with $r\ge2$, each vertex pair belongs to at most one edge. Since each edge contains $\binom r2$ pairs,

$$ |E(H)|\binom r2\le\binom n2. $$

The Fano plane attains equality: $7\cdot3=21=\binom72$. This is an exact finite incidence bound, not a positive constant-density bound as $n$ grows. For fixed $r\ge3$, a linear hypergraph has only $O(n^2)$ edges, whereas the complete $r$-graph has order $n^r$ edges.

Exercise. Show that a linear 3-graph on six vertices has at most five edges. Hint: divide the 15 available pairs by the three pairs per triple. Solution: $3|E(H)|\le15$. This necessary bound alone does not establish that five edges can be realized.

20.6 Hypergraph Ramsey theory

Vertex coloring and edge coloring answer different questions. In hypergraph Ramsey theory, color every edge of the complete $r$-graph and seek a vertex set whose $r$-subsets all have one color. Define $R_r(s)$ to be the least $N$ such that every red-blue coloring of $\binom{[N]}r$ contains a monochromatic $K_s^{(r)}$, for $s\ge r$.

For $r=2$, this is ordinary graph Ramsey theory. For $r=3$, a monochromatic tetrahedron requires four triples of the same color on four vertices. Coloring each vertex instead would be a property-B problem, not this Ramsey problem.

Solved small coloring. On $[5]$, color a triple red if it contains vertex 1 and blue otherwise. The four triples on $\{2,3,4,5\}$ are all blue, giving a monochromatic tetrahedron. A four-set containing 1 has three red triples and one blue triple. This identifies exactly where the monochromatic pattern occurs in this coloring; it is not a proof that every coloring on five vertices has one.

Why Ramsey numbers are finite. The following reservoir argument gives an explicit, deliberately loose recursion. For $r\ge2$ and $s\gt r$, put $M=R_{r-1}(s-1)$, taking $R_1(t)=2t-1$ for two-colored vertices. Then

$$ R_r(s)\le(M+1)2^{\binom M{r-1}}. $$

Start with that many vertices. Select $v_1,\ldots,v_M$ one at a time, retaining a reservoir of future vertices. Whenever a new $(r-1)$-subset $S$ of selected vertices is completed, split the reservoir according to the color of $S\cup\{x\}$ and keep a largest color class. There are at most $Q=\binom M{r-1}$ such halvings. Selecting vertices subtracts at most $M$ from the final lower bound, so at least $N/2^Q-M\ge1$ reservoir vertex survives.

Each $(r-1)$-set now has a fixed extension color. Ramsey's theorem in uniformity $r-1$ gives $s-1$ selected vertices whose $(r-1)$-sets all have one extension color. Adjoin a final reservoir vertex. Every $r$-set containing it has that color by construction; every $r$-set entirely among the selected $s-1$ vertices has the color fixed by its first $r-1$ vertices. Thus the resulting $s$ vertices are monochromatic. Together with $R_r(r)=r$ and the vertex-coloring base case, this proves finiteness by induction.

Exercise. Using $R_2(3)=6$, calculate the bound this argument gives for $R_3(4)$. Hint: $Q=\binom62=15$. Solution: $R_3(4)\le7\cdot2^{15}=229376$. This is a valid existence bound, not an exact value or a claim about the best known bound.

20.7 Hypergraph regularity and removal methods

Optional research extension. This section is not required for the chapter foundation or final investigation. Sections 19.7 and 19.8 introduce the graph regularity-and-removal strategy: approximate structure, count configurations, and remove a small exceptional set. Hypergraphs require additional levels of structure. A full primary treatment is Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem; a complementary formulation is Tao, A variant of the hypergraph removal lemma.

For a 3-graph, partitioning vertices and recording the density of triples between vertex classes does not by itself control all correlations among overlapping triples. Regularity methods also organize pairs between classes, and then measure triple densities relative to those pair structures. The resulting complex records compatible objects at several subset sizes. Higher uniformity requires further levels. This is why substituting triple counts into the graph regularity lemma is not a proof of a hypergraph version.

The hypergraph removal lemma is an established qualitative theorem. Fix an $r$-uniform hypergraph $F$ on $h$ vertices with at least one edge. For every $\eta\gt0$, there exist $\delta\gt0$ and $n_0$ such that an $r$-graph $H$ on $n\ge n_0$ vertices with at most $\delta n^h$ labeled injective copies of $F$ can be made $F$-free by deleting at most $\eta n^r$ edges. A labeled injective copy is an injective map from $V(F)$ to $V(H)$ preserving all edges, so several labelings of the same vertex set are counted separately.

The scales and quantifiers are essential: a proportion of copies is measured against $n^h$, a proportion of edits against $n^r$, and $\delta$ is chosen after $\eta$ and $F$. The statement gives no license to set $\delta=\eta$, or to infer a small absolute number of edits from a small absolute number of copies.

Solved example. Take $t$ vertex-disjoint tetrahedra and no edges between them. Then $n=4t$, there are $4t$ edges, and there are exactly $t$ unlabeled tetrahedra, or $24t$ labeled injective copies. One must delete at least one edge from each component, and doing so suffices. The exact removal cost is therefore $t$, although

$$ \frac{24t}{(4t)^4}=\frac{3}{32t^3},\qquad \frac{t}{(4t)^3}=\frac{1}{64t^2} $$

both tend to zero. The example agrees with the lemma's normalized scales; it does not determine its general dependence of $\delta$ on $\eta$.

Proof sketch, with prerequisites omitted. Regularize a suitable complex, discard exceptional edges, and apply a counting lemma to the remaining structured cells. If a forbidden configuration still survives, the counting lemma forces many labeled copies, contradicting the assumed bound. The omitted ingredients are the multilevel regularity lemma, its parameter hierarchy, and a relative counting lemma. None follows merely from the elementary averaging proof of Turán-density existence in Section 20.4. The cited papers supply those ingredients; this sketch explains their roles rather than claiming to prove them.

Exercise. For two disjoint tetrahedra, find the number of edges, labeled copies, and minimum deletions. Hint: work independently in each component. Solution: there are eight edges, $2\cdot24=48$ labeled copies, and exactly two necessary deletions. Leaving one component untouched leaves a tetrahedron.

20.8 Hypergraph containers

Optional advanced elective. Section 22.1 is recommended later background for probabilistic counting, but finite subset counting is enough for the example here. Container arguments compress a large collection of independent sets into fewer larger sets that have controlled edge content. Full treatments are Saxton and Thomason, Hypergraph containers and Balogh, Morris, and Samotij, Independent sets in hypergraphs.

Write $\mathcal I(H)$ for the independent sets of $H$. A container family $\mathcal C$ covers these sets if

$$ \forall I\in\mathcal I(H)\quad\exists C\in\mathcal C\quad I\subseteq C. $$

Useful container theorems balance two goals: keep $\mathcal C$ small, and make every induced hypergraph $H[C]$ have few edges relative to $H$. Containers need not be independent, and their sizes need not all be equal. The family $\{V(H)\}$ satisfies coverage trivially, but generally supplies no useful edge reduction.

To see the hypotheses that make compression possible, let $N=|V(H)|$, let $d=r|E(H)|/N$ be the average degree, and define

$$ \Delta_j(H)=\max_{S\in\binom{V(H)}j}d_H(S),\qquad 2\le j\le r. $$

Codegree conditions control whether many edges are concentrated around the same small subset. In standard container results these quantities must be small relative to $d$ at appropriate powers of a chosen sparsity parameter. Under those hypotheses, a container can be described using small vertex subsets called fingerprints, together with a reconstruction rule. This is an established theorem framework; a full quantitative statement needs its explicit codegree conditions and constants. We do not apply it to arbitrary sparse examples merely because they are uniform.

Solved exact toy model. Let $H$ consist of $q$ disjoint triples. An independent set must omit at least one vertex from every triple. Choose one omitted vertex per triple, and let $C$ be the complement of these $q$ chosen vertices. There are $3^q$ such containers, each of size $2q$, and each is independent. Every independent set is contained in one: choose an omission from each triple outside that set.

The exact number of independent sets is $7^q$, since each triple has seven proper subsets. The elementary container upper bound gives

$$ |\mathcal I(H)|\le\sum_{C\in\mathcal C}2^{|C|}=3^q2^{2q}=12^q. $$

It overcounts sets lying in several containers, as an upper bound may. For $q=2$, the construction gives nine containers of size four, covering exactly 49 independent sets, with an aggregate bound of 144. This explicit model illustrates coverage; its average degree is only 1, so it is not evidence for strong compression under the high-degree codegree hypotheses of general theorems.

Application to forbidden configurations. Form an auxiliary 3-graph whose vertices are the $\binom n2$ edges of $K_n$ and whose hyperedges are the three-edge sets of its triangles. Independent vertex sets in this auxiliary hypergraph correspond exactly to triangle-free graphs on the original $n$ labeled vertices. Thus containers for hypergraph independent sets can count ordinary graphs avoiding a pattern. Keep the two kinds of vertices distinct: an auxiliary vertex is an original graph edge. On three original vertices, the auxiliary hypergraph has three vertices and one edge, giving seven triangle-free graphs.

Exercise. For three disjoint triples, count the toy containers, their size, and the exact independent sets. Hint: multiply the choices for each component. Solution: there are 27 containers of size six and $7^3=343$ independent sets; the aggregate bound is $27\cdot64=1728$.

20.9 Hypergraph expansion and pseudorandomness

Optional advanced elective. Section 31.10 is recommended later background for expansion and pseudorandomness; it is not needed for the parity example below. In graphs, several familiar quasirandom conditions are equivalent. Hypergraphs admit multiple inequivalent notions, depending on which subset levels and configurations are tested. See Aigner-Horev, Conlon, Hàn, Person, and Schacht, Quasirandomness in hypergraphs for a full primary treatment. A condition must be stated before one uses the word pseudorandom as a hypothesis.

Even expansion needs a convention. For this section, define an outside extension neighborhood of $S\subseteq V(H)$ by

$$ N_H(S)=\{v\in V(H)\setminus S:\ \exists e\in E(H),\ v\in e,\ e\setminus\{v\}\subseteq S\}. $$

For graphs this is the usual outside neighborhood. In a 3-graph, it records vertices completing a pair inside $S$. A singleton has no such neighbors. Therefore a proposed inequality $|N_H(S)|\ge c|S|$ must specify an applicable range of sets, such as $2\le|S|\le k$, and cannot be copied unchanged from a graph statement covering singletons.

Density is a different statistic, and it does not force these local neighborhoods to be large. For example, a dense hypergraph supported on one portion of the vertices can leave the remaining vertices isolated. Degrees, codegrees, extension counts, and counts of selected configurations test different aspects of randomness.

Solved correlation example. Assign each unordered pair $uv$ an independent fair bit $b_{uv}\in\{0,1\}$. Declare $uvw$ an edge exactly when

$$ b_{uv}+b_{uw}+b_{vw}\equiv1\pmod2. $$

Each triple is an edge with probability $1/2$. However, on any four vertices, the sum of the four triple parities is zero modulo 2, since each pair bit appears twice. Consequently a four-set always contains an even number of edges. In the model that independently chooses each triple with probability $1/2$, this constraint does not occur.

For four vertices, there are $2^6=64$ pair-bit assignments. The three triple parities involving a fixed vertex can be prescribed arbitrarily: setting the three pair bits incident to that vertex to zero leaves three free opposite-pair bits prescribing them. The fourth parity is their sum. Thus the eight even-parity patterns each occur eight times. Exactly eight assignments give all four edges, so

$$ \Pr(K_4^{(3)}\text{ is present})=\frac18, $$

whereas independent triple choices give $1/16$. Both models have expected density $1/2$, yet different tetrahedron counts. In fact distinct triple indicators in the pair-bit model are pairwise independent, giving edge-count variance $\binom n3/4$; Chebyshev's inequality then shows density tends to $1/2$ in probability as $n$ grows. Density concentration still does not erase the four-triple correlation.

A fully specified four-vertex instance. Set $b_{12}=1$ and every other pair bit to zero. The hyperedges are 123 and 124. Hence $N_H(\{1,2\})=\{3,4\}$, but $d_H(\{3,4\})=0$. Its density is $2/4=1/2$, with visibly uneven local behavior. This does not assert that every notion of quasirandomness is equivalent to local codegree balance; it shows why a global edge count alone cannot settle a stronger question.

Exercise. Set $b_{12}=b_{34}=1$ and all other pair bits to zero. Which triples occur? Hint: every triple on these four vertices contains exactly one of the two marked pairs. Solution: all four triples occur, so this particular outcome is the tetrahedron. The model's expected density is not a requirement on each outcome.

20.10 Extremal hypergraph constructions

An extremal construction supplies a lower bound by displaying a family with many edges and checking the forbidden configuration. An extremal theorem also requires an upper bound. We will compare three 3-uniform families and prove their properties directly.

Balanced complete multipartite construction. Partition $V$ into $A,B,C$, of sizes $a,b,c$, and include every triple with one vertex in each part. The edge count is $abc$. No four vertices span a tetrahedron: some two lie in the same part, and any triple containing both is absent. For $a=b=c=q$,

$$ \frac{q^3}{\binom{3q}{3}}\longrightarrow\frac29. $$

On six vertices, use $A=\{1,2\}$, $B=\{3,4\}$, $C=\{5,6\}$. There are eight edges. The disjoint edges 135 and 246 show $\nu=2$, the largest possible since each edge uses three of the six vertices. Each part is a cover of size two, and $\nu\le\tau$ shows $\tau=2$. Color $A$ red and the other parts blue: every edge has both colors, proving property B.

Intersecting star. On $[n]$, include every triple containing vertex 1. There are $\binom{n-1}{2}$ edges, and $\nu=\tau=1$ whenever $n\ge3$. A four-set containing 1 is missing its triple avoiding 1; a four-set avoiding 1 has no edges. Thus the star is tetrahedron-free. Coloring the center red and the other vertices blue proves property B. Its density is

$$ \frac{\binom{n-1}{2}}{\binom n3}=\frac3n, $$

which tends to zero despite its optimality for the different problem of forbidding two disjoint triples. On six vertices it has ten edges. A construction can be extremal for one forbidden family without having positive limiting density.

Cyclic three-part construction. Partition $V$ into $A,B,C$ and include precisely the types

$$ ABC,\qquad AAB,\qquad BBC,\qquad CCA. $$

Here AAB means two distinct vertices from $A$ and one from $B$; the order of letters does not order the vertices. The part containing the repeated pair points cyclically to the next part. The edge count is

$$ abc+\binom a2b+\binom b2c+\binom c2a. $$

Proof of tetrahedron-freeness. Classify a four-set by its occupancy of the three parts. Type $4$ or $3+1$ has a triple inside one part, which is absent. For type $2+2$, only one of the two directions between its occupied parts is allowed, so some triple is absent. For type $2+1+1$, the duplicated part points to just one of the singleton parts; the triple using its pair and the other singleton is absent. These possibilities exhaust all distributions of four vertices among three parts.

For equal part sizes $q$, the edge count is

$$ q^3+3q\binom q2=\frac{5q^3-3q^2}{2},\qquad \frac{(5q^3-3q^2)/2}{\binom{3q}{3}}\longrightarrow\frac59. $$

Together with the existence of the Turán-density limit, this proves $\pi(K_4^{(3)})\ge5/9$. This chapter claims only this construction lower bound; no exact asymptotic value or current best upper bound is needed for its proof.

Solved six-vertex case. With the same two-vertex parts as above, the 14 edges are

$$ \{135,136,145,146,235,236,245,246,123,124,345,346,156,256\}. $$

The six absent triples are 125, 126, 134, 234, 356, and 456. Every four-set contains an edge: its part occupancy is either $2+2$, giving two included triples, or $2+1+1$, giving three. Therefore $\alpha\le3$; the absent triple 125 shows $\alpha=3$ and $\tau=3$. A cover is its complement $\{3,4,6\}$. The matching 135, 246 proves $\nu=2$.

This family has no weak two-coloring. If a color class has at least four vertices, it contains an edge. Otherwise both classes have size three and would both have to be absent triples. But the complement of each of the six absent triples is an included triple. Hence no such split works. Coloring the three parts with three colors works, since no edge lies within a part. Its weak chromatic number is exactly 3.

Exercise. Verify the complement argument explicitly for 125 and 356, and find the construction's density on six vertices. Hint: subtract each triple from $[6]$. Solution: the complements are 346 and 124, both edges. The density is $14/\binom63=7/10$. A finite density of $7/10$ need not equal the asymptotic density $5/9$ of its growing balanced versions.

Construct a hypergraph and investigate matching, coloring, and density

The investigation compares three families on the same vertex set so that changing a definition cannot disguise a structural difference. Uniformity fixes the denominator for density and bounds matching size, while the construction determines which triples actually occur. Rank alone would not identify either the edge list or its coloring behavior.

Worked solution table. All three families are tetrahedron-free, but their matching, cover, and coloring behavior differ.

For $T$, a part of size two is a cover and its four-vertex complement is independent. For $S$, the center is a cover and its complement is independent. For $C_*$, the absent triple 125 is a largest independent set and 346 is a minimum cover. Section 20.10 gives the matching and coloring proofs. Since each family has an edge, one color never suffices.

The degree sequences provide an independent count check:

$$ T:(4,4,4,4,4,4),\qquad S:(10,4,4,4,4,4),\qquad C_*:(7,7,7,7,7,7). $$

Their sums are 24, 30, and 42. The enumeration counts for valid red-blue assignments, counting the two color names as distinct, are respectively 18, 12, and 0. For $T$, each color class must omit a part; valid assignments either make all three parts monochromatic with both colors present (six assignments), or split one part and make the other two parts opposite monochromatic colors ($3\cdot2\cdot2=12$ assignments). Splitting two parts fails because whichever color occurs in the third part then meets all three parts. For $S$, choose the center's color, and give that same color to at most one of the five other vertices, giving $2(1+5)=12$. The cyclic count is zero by the complement proof.

Reproducible search outline. Represent a vertex subset by a six-bit mask. It is independent exactly when it contains no edge mask, and it is a cover exactly when it intersects every edge mask. For a red mask $R$, its blue mask is the complement within the six vertices; accept a coloring exactly when both masks are independent. A four-set is a tetrahedron exactly when all its four triples belong to the edge family. For matchings, checking pairs of edges suffices here because no three disjoint triples fit into six vertices. The same shortcut would be invalid on larger vertex sets.

This search exhausts each finite instance and can certify its numerical invariants when correctly implemented. The preceding proofs also explain the structure and extend where appropriate. Neither a six-vertex computation nor a density comparison establishes an asymptotic extremal theorem.

Application. Suppose each vertex is a task, and an edge is a triple that overloads a shared resource when run simultaneously. An independent set is a feasible batch under these specified triple constraints. A cover identifies tasks whose postponement hits every overload triple; a weak two-coloring assigns tasks to two feasible batches. If pairs remain safe, replacing every triple by three pairwise conflicts would incorrectly reject safe two-task batches. If hyperedges instead represent resource bundles to be chosen, a matching selects mutually disjoint bundles. State the interpretation before using the invariant: a matching of conflict triples has a different operational meaning from a feasible independent batch.

Optional extension. Change the three part sizes and compare density, degrees, and pair codegrees with the balanced case. For each experiment state a precise conjecture about your finite family, then prove it or find a counterexample. Alternatively, enumerate all $2^{20}$ 3-graphs on six labeled vertices and optimize edge count subject to tetrahedron-freeness; explain why even a verified finite optimum would not settle the limiting problem. These are construction and computation projects, not assertions about the current status of an open research question.