Two Stability Theorems for Kℓ+1r‐Saturated Hypergraphs

ABSTRACT Let be a family of ‐uniform hypergraphs (henceforth ‐graphs). An ‐saturated ‐graph is a maximal ‐graph not containing any member of as a subgraph. For integers , let be the collection of all ‐graphs with at most edges such that for some ‐set every pair is covered by an edge in , and let be the complete ‐partite ‐graph on vertices with no two part sizes differing by more than one. Let be the number of edges in . Our first result shows that for each every ‐saturated ‐graph on vertices with edges contains a complete ‐partite subgraph on vertices, which extends a stability theorem for ‐saturated graphs given by Popielarz, Sahasrabudhe, and Snyder. We also show that the bound is best possible. Our second result is motivated by a celebrated theorem of Andrásfai, Erdős, and Sós, which states that for every ‐free graph on vertices with minimum degree is ‐partite. We give a hypergraph version of it. The minimum positive co‐degree of an ‐graph , denoted by , is the maximum such that if is an ‐set contained in an edge of , then is contained in at least distinct edges of . Let be an integer and be a ‐saturated 3‐graph on vertices. We prove that if either and ; or and , then is ‐partite; and the bound is best possible. This is the first stability result on minimum positive co‐degree for hypergraphs.