WorksMathematics
Stability and exact extremal colourings for the Alon–Frankl–Lovász bound
Abstract
The Alon–Frankl–Lovász theorem states that every -colouring of the edges of the complete -uniform hypergraph on vertices contains a monochromatic matching of size . For fixed uniformity and number of colours , we prove a stability theorem: every colouring whose largest monochromatic matching has size at most differs from a threshold extremal colouring on only edges. We also give a necessary and sufficient structural characterization of all extremal colourings for sufficiently large . The proofs combine rigidity of fractional covering weights with an extension argument for prescribed matchings. These results answer, for sufficiently large orders, the stability and extremal-colouring questions posed by Gishboliner, Glock, Michaeli and Sgueglia.
Introduction
Packing vertex-disjoint monochromatic subgraphs is a natural theme in Ramsey theory. One instance is the search for a monochromatic matching, a collection of pairwise disjoint edges of the same colour. The size of such a matching depends strongly on how the edges of that colour are distributed: even a large family of edges may contain only small matchings if every edge meets a fixed small set of vertices. In a colouring of a complete graph or hypergraph, the colour classes partition the entire edge set, so restrictions on their matching numbers must be satisfied simultaneously. This interaction between disjointness within each colour and the requirement to colour every edge makes monochromatic matchings a natural meeting point of Ramsey theory and extremal set theory.
For a positive integer , write , and let denote the family of -element subsets of . An -graph is an -uniform hypergraph, and is the complete -graph on vertices. A matching is a set of pairwise vertex-disjoint edges; its size is its number of edges. Write for the maximum size of a matching in . For a colouring , let be the spanning -graph with edge set . Throughout, are fixed and . Put
The definition of gives , . The Alon–Frankl–Lovász theorem [2] asserts that
This bound is sharp for every . We call a colouring extremal if equality holds, equivalently if for every .
The graph case is the equal-size case of the matching Ramsey theorem of Cockayne and Lorimer [6]. More generally, the bound has a natural Kneser-hypergraph interpretation: if has vertex set and hyperedges consisting of pairwise disjoint -sets, then a -colouring of with no monochromatic matching of size is precisely a proper -colouring of . The case goes back to the proofs of Kneser’s conjecture by Lovász [16] and Bárány [3]. The general result of Alon, Frankl and Lovász [2] belongs to this topological tradition; see Matoušek [18] for background.
Gishboliner, Glock, Michaeli and Sgueglia [12 Section 4] asked for a stability theorem and a characterization of the extremal colourings. We prove the stability statement and obtain an exact characterization for all sufficiently large , in every residue class modulo .
Threshold colourings
The extremal constructions are described by positive integer thresholds whose sum is . Set
Every such vector satisfies
The upper bound follows from for the other coordinates.
Definition 1.1. Let be the family of colourings for which there are and a partition into possibly empty parts such that
A colour with is eligible for . Each edge may be assigned any of its eligible colours; no compatibility condition is imposed on different edges.
For each , such colourings exist and are extremal. Indeed, the capacities are nonnegative and have sum , so a partition respecting them exists. Every -edge has an eligible colour, since otherwise its size would be at most . Finally,
and (1.2) gives equality for the maximum over colours. For any partition in Definition 1.1,
The first assertion follows because the nonnegative capacity deficits sum to ; the second follows from .
The two results
For two colourings on the same vertex set , define
Theorem 1.2 (Edge-edit stability). For every , there are and such that every colouring with and
satisfies .
Equivalently, for a sequence with ,
The stability theorem permits exceptional edges. Our second result describes exactly which exceptions are possible when . The quantity is the total unused capacity of a threshold partition, and the integers below distribute this unused capacity among the colours.
Theorem 1.3 (Exact normal form). There is such that, for every , a colouring is extremal if and only if there are , nonnegative integers , and a partition with
such that, for each , the family of violating edges
satisfies
For colour , it suffices to check matchings in with at most edges. The sufficiency holds for every for which the stated partition exists.
The positive integer is the deficit of a violating colour- edge. Thus the theorem places a budget on the total deficit of disjoint violating edges. The number of edges in each test is bounded independently of ; the total number of violating edges need not be bounded. Neither the threshold vector nor the partition is asserted to be unique.
Related work and proof strategy
The extremal-colouring problem is related to, but distinct from, the Erdős matching problem [7]: the latter asks for the maximum size of a single -uniform family with prescribed matching number, whereas here all colour classes partition and must simultaneously have small matching number. Important bounds for the single-family problem were obtained by Frankl [8] and Frankl and Kupavskii [10]. Their two basic constructions, a family meeting a fixed small set and a complete -graph on a restricted vertex set, correspond to the endpoint conditions and in our threshold rule. More general families defined by a lower bound on the intersection with a fixed set also feature in the complete intersection theorem of Ahlswede and Khachatrian [1] and the union-restricted families studied by Frankl and Kupavskii [9]. These analogies explain the relevance of intersection thresholds, but do not by themselves classify extremal colourings.
Stability results for bounded matching number provide further context. In particular, Frankl, Lu, Ma and Wu [11] proved a stability theorem for 4-uniform hypergraphs as part of their work on the Erdős matching conjecture. Their single-family extremal problem differs from the simultaneous multicolour problem considered here.
The proof has two stages. In the stability stage, weak regularity and fractional matching duality associate a vector of covering weights with each cluster. Near equality in the AFL bound forces almost all these vectors to lie near the axis points , with proportions . These clusters give the required vertex partition; a small adjustment enforces its exact capacity bounds.
The exact stage begins with this approximate partition. Removing a small set of exceptional vertices leaves cores in which the number of edges of an incorrect colour through any vertex is . Each exceptional vertex is assigned a colour that occurs on a positive proportion of its baseline links to the cores. A switching argument then completes any prescribed bounded matching whenever the relevant capacity inequality fails. Applying this argument first to the empty matching gives the exact part capacities, and applying it to matchings of violating edges gives the deficit budgets.
The threshold constructions already appear in the discussion of Gishboliner, Glock, Michaeli and Sgueglia [12, Section 4]. Our proofs build on the convex compression, integer-threshold rigidity, profile switching and exceptional-vertex completion mechanisms of Liu, Turevskii, Wang and Yan [15]; these mechanisms are not claimed as new here. Weak hypergraph regularity has its origins in the work of Chung [5]; its use for embedding linear hypergraphs was developed by Kohayakawa, Nagle, Rödl and Schacht [14]. Fractional matching and covering are standard linear programming tools; we refer to Schrijver [20] for a systematic treatment. We give proofs of the rigidity and completion statements in the forms needed for our results. Section 2 proves the covering-weight lemma, Section 3 proves stability, and Section 4 derives the exact normal form.
The defect and random-host extensions form another direction. Gishboliner, Glock, Michaeli and Sgueglia [12] establish an asymptotic AFL bound for almost complete hypergraphs and transfer it to sparse random hypergraphs. In the graph setting, Gishboliner, Krivelevich and Michaeli [13] obtained a random-host matching result in their study of colour-biased Hamilton cycles. These results concern the persistence of large monochromatic matchings when the host is incomplete; our theorems describe near-extremal and exact colourings of the complete host.
For graphs, Xu, Yang and Zhang [21 Theorem 2] characterized the critical complete-graph colourings for matching Ramsey numbers, allowing unequal prescribed matching sizes. Their proof uses the Gallai–Edmonds decomposition; see Lovász and Plummer [17] for the underlying graph matching theory. Our exact statement concerns all sufficiently large orders for fixed . No explicit value of is supplied.
We write and for the th coordinate vector. The support of a probability measure is its closed topological support. All asymptotic statements keep fixed. A partition may have empty parts unless nonemptiness is explicitly required. For a partition and an edge , the vector is the profile of $e.
Rigidity of near-critical covering weights
The following finite statement is the only rigidity input used in the stability proof. It says that near-optimal covering weights concentrate near a finite collection of axis points with integer reciprocals. The compactness argument below proves the required uniform finite statement without providing an explicit bound on its parameters.
Lemma 2.1 (Robust cover clustering). For every there is such that the following holds. Let be a positive integer and let satisfy
For independent uniform indices , sampled with replacement, suppose that
Put . There is such that the sets () and form a partition of and satisfy
Proof. Suppose the lemma fails for some . For each positive integer , take a counterexample with and form its empirical measure , where denotes the unit point mass at . Probability measures on the compact cube have a weakly convergent subsequence; this is the compact-space case of Prokhorov’s theorem, as presented in Billingsley [4]. Write along such a subsequence and .
Step 1: an exact covering problem on the support. Coordinate functions are continuous, so (2.1) implies
We claim that, for all , including repetitions,
If this failed, continuity would give relative open neighbourhoods of whose entire Cartesian product violates the inequality. Each because . The Portmanteau theorem [4] gives . Independent sampling would therefore violate the inequality with probability at least , bounded away from zero. This contradicts (2.2). The same argument works when some of the support points coincide.
Step 2: the covering condition forces integer thresholds. Let . Since is compact and the ambient space is finite-dimensional, is compact. Choose minimizing . The barycentre belongs to , since is closed and convex and contains the support of . Thus for each , we have .
If has affine dimension at most , Carathéodory’s theorem [19] represents using at most points of . If has dimension , then is on its boundary: otherwise for small , contrary to minimality. Take a supporting hyperplane through , using the supporting-hyperplane theorem [19]. In any finite convex representation of by points of , every point with a positive coefficient lies in that hyperplane, because all points of lie on one side. Carathéodory’s theorem in this face again uses at most points. Thus, omitting zero coefficients, we have , , , , and .
Set , a nonnegative integer strictly smaller than . If , choose integers with . Apply (2.5) to copies of each . For some coordinate , , a contradiction. The middle inequality is strict because every , all coordinates are nonnegative, and the first sum has a positive term. Therefore . Equality holds throughout. Hence and , so every is a positive integer. Their sum is .
Step 3: identify the support and its masses. For each , the profile is nonnegative and has sum . By (2.5), some coordinate satisfies . Equality throughout gives and for . Since , it also gives . The coordinates are all distinct: if with , the latter equality for contradicts the zero forced by the equality for . Since is a permutation of , relabel the selected support points and their associated integers so that . All coordinates have been used, and therefore for every , we have .
For any , apply (2.5) to the following support points: copies of for each . In coordinate , their sum is . Thus for some . Consequently
by (2.4). Thus on : a support point with would, by continuity, have a positive-measure neighbourhood on which exceeds one by a fixed amount. Combining with and nonnegativity gives . If is the mass at , then by (2.4). Since , all these bounds are equalities:
Finally, the open balls of radius around the axis points are disjoint: their centres have -distance at least . Their boundaries contain no atom of (2.6). Weak convergence gives and . For large this is (2.3), contradicting the choice of the counterexamples.
Proof of stability
We first obtain covering weights from a regular partition. Lemma 2.1 then identifies the parts, and an elementary repair puts their sizes within the exact capacities.
Regularity and fractional matching lift
For disjoint nonempty sets , let be the number of edges of meeting each set once, divided by . The tuple is -regular in if
whenever and for all . A partition is equitable if its part sizes differ by at most one.
This is the vertex-partition notion of weak hypergraph regularity studied in [5, 14]. We use the following dense multicolour form. It is [12 Lemma 3.1] with , where the upper uniformity assumptions hold automatically with, for example, upper-density bound 2. If needed, increase the prescribed lower bound on the number of parts before applying that lemma.
Lemma 3.1 (Weak regularity). For every and integer , there are integers such that any -uniform hypergraphs on a common vertex set of size admit an equitable partition , with , such that, for every , at most of the unordered -tuples of distinct parts fail to be -regular in .
Call a tuple jointly regular if it is regular in every colour. At most tuples are not jointly regular. Fix . Given an equitable partition of a colouring, define an -graph on for each by
All colours of density at least are retained; the may overlap. This is important: an edge of density at least in colour must be retained in , even if it also belongs to another . Since the colour densities sum to one, every jointly regular tuple belongs to at least one .
A fractional matching in an -graph assigns nonnegative weights to its edges so that the sum at each vertex is at most one. A fractional vertex cover assigns nonnegative weights to its vertices so that the sum on every edge is at least one. Linear programming duality, in its standard fractional packing–covering form [20], gives
The upper bounds cause no loss: truncating a larger coordinate at one preserves every cover constraint.
Lemma 3.2 (Fractional matching lift). Let be defined by (13), with . Suppose the clusters have size or , where is a positive integer. Then
Proof. Take an optimal fractional matching in . For each , set a demand of colour- edges across its clusters. Process these demands in any order, choosing every edge disjoint from all edges already chosen. The total demand on a cluster is at most
At every stage each cluster has at least unused vertices. Since gives , each unused set is large enough for regularity. For the current tuple the colour- density on its unused sets is at least , so the next edge exists. The resulting matching has size
The total rounding loss is therefore at most the number of edges of the reduced hypergraph.
Repairing the part sizes
Lemma 3.3 (Partition repair). Let and . Suppose at most edges of violate . Put . Then
Proof. The capacities sum to , so the total unused capacity in underfull parts is . Move exactly vertices from overfull parts to underfull parts without exceeding a receiving capacity. Edges avoiding the moved vertices retain their intersection profiles. Thus at most the original violations and the edges meeting a moved vertex need recolouring. Recolour every such edge whose original colour is ineligible with any eligible colour. Such a colour exists by (1.3), and the new partition respects the capacities. At most edges meet a moved vertex, proving (3.3).
Proof of the stability theorem
Proof of Theorem 1.2. We may assume . Throughout this proof, the parameters in (1.1) are computed from the current order .
Step 1: parameter selection. Set and obtain from Lemma 2.1; decrease it so that . Choose . Next choose so that , , and . This is possible because the last fraction tends to as . Take an integer , and apply Lemma 3.1 to obtain . Finally choose so large that, for every , , , and
The last requirement is possible because its left side tends to , which is less than . Thus all constants, including , have been fixed before .
Step 2: obtain the threshold vector from cover weights. Let satisfy the theorem’s assumptions, and take a regular partition with and cluster sizes or , where . Define all the by (3.1) and choose optimal covers . By (3.2) and Lemma 3.2,
Here . For independent uniform indices , the probability of a repetition is at most . Conditional on being distinct, their underlying -set is uniform. If it is jointly regular, it belongs to some and hence has cover sum at least one in that coordinate. Thus, for ,
Lemma 2.1 now gives and satisfying (2.3).
Let and . Equitability gives , and . For the second bound, replacing each cluster size by changes the sum over by at most . Assign arbitrarily to the parts, obtaining a partition of with
Step 3: bound every violation of the threshold rule. Consider a jointly regular tuple of clusters in , and put . By the definition of the clusters , each differs from by less than when , and is less than otherwise. Hence
If , then, since ,
The cover constraint rules out . Joint regularity and (3.1) therefore imply that its colour- density is less than . Summing over ineligible colours, the wrong-colour density on this tuple is at most .
Every threshold violation either meets , uses a cluster twice, lies in a tuple that is not jointly regular, or is one of the low-density wrong-colour edges just counted. Their total number consequently satisfies
Here and . Thus the middle term is at most , and the last term is at most . Therefore
Finally, , so . (16) gives
Applying Lemma 3.3 and , we obtain
The three terms are each at most by the choices of , , and . This proves the theorem. □
From stability to the exact normal form
We prove sufficiency first. For necessity, we isolate one completion inequality: its empty-matching case gives the part capacities, and its nonempty cases give the deficit budgets.
Sufficiency and bounded witnesses
Proof of the sufficiency in Theorem 1.3. Suppose (1.5)–(1.6) hold. If were a colour- matching with edges, then
a contradiction. Thus every colour has matching number at most , and (1.2) makes the colouring extremal.
To justify the bounded tests, take an inclusion-minimal matching violating (1.6). If it had more than edges, any of them would already have total deficit at least , since the deficits are positive integers. This would contradict minimality. Thus a violation has a witness of at most edges. □
A profile switching lemma
Let be a nonnegative integer vector of sum , and let be a positive integer. For disjoint sets of sizes , write
For an edge family , let and . The following form of the switching argument of [15] gives an explicit sufficient bound on the maximum degree of a forbidden edge family. In the proof, we call the edges of bad and the other edges good.
Lemma 4.1 (Profile switching). Allow when . If and satisfies
then contains a perfect matching of size . In particular, suffices as .
Proof. For each , write as the disjoint union of labelled blocks of size (all empty if ). Unite blocks with the same label. This gives a perfect matching in the complete profile hypergraph. Choose one, , with as few bad edges as possible, and suppose .
Divide the positions into groups of sizes . Label the vertices of every edge of by these positions, so that the same positions always belong to the same part . Fix all labels before making the following choices.
Choose ordered distinct edges . For , let be the vertex in position of . Put
Each new edge has one vertex from each position, hence the correct profile. The new edges are disjoint, cover the same vertices as the selected old edges, and contains the fixed vertex .
For a fixed , any prescribed edge arising as determines at most one ordered tuple of old edges. Each of its vertices identifies its old matching edge and its fixed position , and hence that edge’s row . At most choices therefore make bad. At most choices make any new edge bad, whereas there are choices in total. By (4.1), one choice has all new edges good. Switching to these edges reduces the number of bad edges, a contradiction. □
One inequality for capacities and deficits
For a matching , write , with . The next lemma refines the exceptional-vertex completion in [15] by allowing an arbitrary bounded matching to be prescribed first. Its contrapositive is the main idea: if a prescribed matching uses too few vertices of , then the remaining vertices of allow it to be extended to a matching of size .
Lemma 4.2 (Bounded matching completion). Fix , , an integer , and . Consider a sequence of -colourings of complete -graphs, with an integer parameter and vertex partitions
Let . Suppose the family of edges in the cores with profile that are not coloured has maximum degree . Let and put . Assume each belongs to at least colour- edges with
Suppose for every member of the sequence. Then, for all sufficiently large members of the sequence, every colour- matching with , including the empty matching, satisfies
The left side of (4.3) may be negative for a general matching. It equals the sum of the positive deficits when every edge of is violating relative to .
Proof. Fix a member of the sequence and a colour- matching with . Set
Then , and . We work with a sufficiently large member of the sequence; the estimates below will be uniform over all such . If (19) fails, integrality gives
For each , choose a colour- edge satisfying (18), disjoint from and the previously chosen edges. This is possible greedily. At most core vertices are forbidden. Each forbidden core vertex excludes at most
candidates through , since . Thus at most of the at least colour- candidates are excluded. The noncore vertex of each edge is its own distinct , outside .
After these choices, we seek further colour- edges of profile . In the th core, the number of remaining vertices minus the number required is
by (20). For , the difference is
For sufficiently large , we have . Choose subsets of the remaining cores having exactly vertices in each . The wrong-colour family on them still has maximum degree . Lemma 4.1 supplies disjoint colour- edges. Together with and the selected links, they form a matching of size , a contradiction. The number of forbidden core vertices is bounded by , independently of the choice of . The switching bound also depends only on the given wrong-colour maximum degree and on . Consequently, one sufficiently large index works simultaneously for all matchings with . □
Necessity of the normal form
Proof of the necessity in Theorem 1.3. Suppose that there are counterexamples for arbitrarily large . Choose such a sequence with , and use from (1). All asymptotic estimates below refer to this sequence.
Step 1: remove vertices with large error degree. Extremality gives . The sequential form of Theorem 1.2 yields with
Let be a witnessing partition for . After passing to a subsequence, its vector is fixed, because there are finitely many such vectors. By (4), .
Write , put , and let and . Since , we have and . An edge in the cores with profile has only colour eligible in . Every such edge not coloured in therefore belongs to . Its wrong-colour family has maximum degree at most .
Step 2: assign the exceptional vertices to colours. For , the number of edges with for every is
Here and . By the pigeonhole principle, one colour occurs on at least of these edges, for a fixed depending only on . Indeed, the leading coefficient of the product above is , with ; there are only finitely many possible vectors . Fix such a colour for each and put
These sets form a partition of .
Step 3: recover the capacities and deficit budgets. Apply Lemma 4.2 with , and , for each . Its hypotheses follow from Steps 1–2 and . Since there are only colours, the conclusions hold simultaneously for all from some index onwards. Hence every colour- matching with at most edges obeys
Taking defines nonnegative integers . Because the partition ,
For a matching of violating colour- edges, disjointness gives . If it violated the budget , the bounded-witness argument at the start of this section would give a violating submatching with at most edges. This contradicts (21).
Thus (1.5)–(1.6) hold for every sufficiently large member of the counterexample sequence. This contradiction proves the existence of and the necessity of the normal form.
Usage of AI tools
The proofs presented in this paper were developed by ChatGPT. The authors take full responsibility for the correctness of the mathematical arguments and for the entire content of the manuscript.
References
School of Mathematics and Statistics, Xi’an Jiaotong University
Email address: [email protected];[email protected]; [email protected]
References
- [1]R. Ahlswede and L. H. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997), 125–136.DOI
- [2]N. Alon, P. Frankl and L. Lovász, The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc. 298 (1986), 359–370.DOI
- [3]I. Bárány, A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A 25 (1978), 325–326.DOI
- [4]P. Billingsley, Convergence of Probability Measures, 2nd ed., Wiley Series in Probability and Statistics, John Wiley & Sons, New York, 1999.
- [5]F. R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 (1991), 241–252.
- [6]E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975), 252–256.DOI
- [7]P. Erdős, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95.
- [8]P. Frankl, Improved bounds for Erdős’ matching conjecture, J. Combin. Theory Ser. A 120 (2013), 1068–1072.DOI
- [9]P. Frankl and A. Kupavskii, Beyond the Erdős matching conjecture, European J. Combin. 95 (2021), Paper No. 103338.
- [10]P. Frankl and A. Kupavskii, The Erdős matching conjecture and concentration inequalities, J. Combin. Theory Ser. B 157 (2022), 366–400.DOI
- [11]P. Frankl, H. Lu, J. Ma and Y. Wu, Towards the Erdős matching conjecture for 4-uniform hypergraphs: stability and applications, arXiv:2602.19230v2, 2026.arxiv.org/abs/2602.19230
- [12]L. Gishboliner, S. Glock, P. Michaeli and A. Sgueglia, Defect and transference versions of the Alon–Frankl–Lovász theorem, Combin. Probab. Comput. 35 (2026), 542–553. Version with Appendix A: arXiv:2503.05089v2.arxiv.org/abs/2503.05089
- [13]L. Gishboliner, M. Krivelevich and P. Michaeli, Color-biased Hamilton cycles in random graphs, Random Structures Algorithms 60 (2022), 289–307.DOI
- [14]Y. Kohayakawa, B. Nagle, V. Rödl and M. Schacht, Weak hypergraph regularity and linear hypergraphs, J. Combin. Theory Ser. B 100 (2010), 151–160.DOI
- [15]H. Liu, M. Turevskii, L. Wang and Z. Yan, Structural reductions for monochromatic matchings and Ramsey tilings, arXiv:2606.24863, 2026.arxiv.org/abs/2606.24863
- [16]L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), 319–324.DOI
- [17]L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, Amsterdam, 1986.
- [18]J. Matoušek, Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer, Berlin, 2003.
- [19]R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton University Press, Princeton, NJ, 1970.
- [20]A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24, Springer, Berlin, 2003.
- [21]C. Xu, H. Yang and S. Zhang, On characterizing the critical graphs for matching Ramsey numbers, Discrete Appl. Math. 287 (2020), 15–20.arxiv.org/abs/1905.08456