Extremal hypergraphs and codegrees

For an s-element set S with s smaller than k, its s-degree is the number of edges containing S. When s equals k minus one, this is the codegree: the number of vertices that can extend S to an edge. The minimum is taken over all such subsets, not only those already lying in some edge. A missing extension therefore contributes a zero codegree. In a three-uniform hypergraph, codegree belongs to a pair, whereas vertex degree counts edges containing one vertex.

The link of a vertex v is the (k−1)-uniform hypergraph whose edges are obtained by removing v from edges containing it. More generally, links translate extension questions into lower-uniformity set systems. Summing all (k−1)-codegrees counts each original edge exactly k times, once for each vertex that can be removed. This gives an immediate lower bound on the number of edges from a minimum-codegree assumption, but it does not describe how those edges overlap.

The hypergraph extremal number ex_k(n,F) is the largest edge count in an n-vertex k-uniform hypergraph avoiding an ordinary copy of fixed F. The natural edge density divides by the number of k-subsets. Complete multipartite constructions still supply examples, but the graph theorem that chromatic number determines asymptotic extremal density has no automatic direct replacement for arbitrary hypergraphs. One must specify the forbidden uniform set system and prove the relevant claim rather than importing an exponent or threshold by analogy.

High vertex degree and high codegree are also different hypotheses. Many edges through every vertex can coexist with a particular pair having no extension. Conversely, a positive minimum codegree gives extension opportunities for every pair in a three-uniform system, but choosing edges greedily can consume vertices needed later. Perfect matching questions require disjoint edges covering every vertex, including the divisibility requirement that k divides the vertex count. Local abundance cannot repair a failed arithmetic condition.

Partition the vertices into A and B and include exactly those three-element edges meeting A in an even number of vertices. Every permitted edge uses either zero or two vertices of A. Any disjoint union of permitted edges therefore covers an even number of A vertices. If A has odd size, no perfect matching can exist, even when the total order is divisible by three. This is a global obstruction visible in arithmetic modulo two.

The codegrees depend on pair type. A pair inside A must be extended by a B vertex; a mixed pair must be extended by a different A vertex; a pair inside B must be extended by another B vertex. Provided both parts are large enough, each type has many extensions. This construction does not disprove a correctly stated sufficiently high-codegree matching theorem. It shows why such theorems must account for sharp thresholds and structural barriers, and why an unspecified phrase such as “dense enough” cannot stand in for a hypothesis.