betaFeedback

WorksMathematics

Stability and exact extremal colourings for the Alon–Frankl–Lovász bound

Abstract

The Alon–Frankl–Lovász theorem states that every qq-colouring of the edges of the complete rr-uniform hypergraph on nn vertices contains a monochromatic matching of size ⌊(n+q−1)/(r+q−1)⌋\lfloor(n+q-1)/(r+q-1)\rfloor. For fixed uniformity rr and number of colours qq, we prove a stability theorem: every colouring whose largest monochromatic matching has size at most n/(r+q−1)+o(n)n/(r+q-1)+o(n) differs from a threshold extremal colouring on only o(nr)o(n^r) edges. We also give a necessary and sufficient structural characterization of all extremal colourings for sufficiently large nn. 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 aa, write [a]={1,…,a}[a]=\{1,\ldots,a\}, and let (Vr)\binom{V}{r} denote the family of rr-element subsets of VV. An rr-graph is an rr-uniform hypergraph, and Kn(r)K_n^{(r)} is the complete rr-graph on nn vertices. A matching is a set of pairwise vertex-disjoint edges; its size is its number of edges. Write ν(H)\nu(H) for the maximum size of a matching in HH. For a colouring χ:(Vr)→[q]\chi:\binom{V}{r}\to[q], let Hi=Hi(χ)H_i=H_i(\chi) be the spanning rr-graph with edge set χ−1(i)\chi^{-1}(i). Throughout, r,q≥2r,q\ge2 are fixed and n=∣V∣≥rn=|V|\ge r. Put

L=r+q−1,k=⌊n+q−1L⌋,m=k+1,D=Lm−q−n.(1)L=r+q-1,\qquad k=\left\lfloor\frac{n+q-1}{L}\right\rfloor,\qquad m=k+1,\qquad D=Lm-q-n. \tag*{(1)}

The definition of kk gives Lk−q+1≤n≤Lk+r−1Lk-q+1\le n\le Lk+r-1, 0≤D≤L−10\le D\le L-1. The Alon–Frankl–Lovász theorem [2] asserts that

max⁡i∈[q]ν(Hi)≥k.(2)\max_{i\in[q]}\nu(H_i)\ge k. \tag*{(2)}

This bound is sharp for every n≥rn\ge r. We call a colouring extremal if equality holds, equivalently if ν(Hi)≤k\nu(H_i)\le k for every ii.

The graph case r=2r=2 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 KG⁡(m)(n,r)\operatorname{KG}^{(m)}(n,r) has vertex set ([n]r)\binom{[n]}{r} and hyperedges consisting of mm pairwise disjoint rr-sets, then a qq-colouring of Kn(r)K_n^{(r)} with no monochromatic matching of size mm is precisely a proper qq-colouring of KG⁡(m)(n,r)\operatorname{KG}^{(m)}(n,r). The case m=2m=2 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 nn, in every residue class modulo LL.

Threshold colourings

The extremal constructions are described by positive integer thresholds whose sum is LL. Set

Cr,q={c∈Z>0q:∑ici=L}.\mathcal{C}_{r,q}=\left\{c\in\mathbb{Z}_{>0}^{q}:\sum_i c_i=L\right\}.

Every such vector satisfies

1≤ci≤r,∑i(ci−1)=r−1.(3)1\le c_i\le r,\qquad\sum_i(c_i-1)=r-1. \tag*{(3)}

The upper bound follows from cj≥1c_j\ge1 for the other q−1q-1 coordinates.

Definition 1.1. Let Er,q(V)\mathcal{E}_{r,q}(V) be the family of colourings ψ\psi for which there are c∈Cr,qc\in\mathcal{C}_{r,q} and a partition into possibly empty parts V=V1⊔⋯⊔VqV=V_1\sqcup\cdots\sqcup V_q such that

∣Vi∣≤cim−1,ψ(e)=i ⟹ ∣e∩Vi∣≥ci.|V_i|\le c_i m-1,\qquad\psi(e)=i\ \Longrightarrow\ |e\cap V_i|\ge c_i.

A colour ii with ∣e∩Vi∣≥ci|e\cap V_i|\ge c_i is eligible for ee. Each edge may be assigned any of its eligible colours; no compatibility condition is imposed on different edges.

For each c∈Cr,qc\in\mathcal{C}_{r,q}, such colourings exist and are extremal. Indeed, the capacities ui=cim−1u_i=c_i m-1 are nonnegative and have sum Lm−q=n+D≥nLm-q=n+D\ge n, so a partition respecting them exists. Every rr-edge has an eligible colour, since otherwise its size would be at most ∑i(ci−1)=r−1\sum_i(c_i-1)=r-1. Finally,

ν(Hi(ψ))≤⌊∣Vi∣ci⌋≤m−1=k,\nu(H_i(\psi))\le\left\lfloor\frac{|V_i|}{c_i}\right\rfloor\le m-1=k,

and (1.2) gives equality for the maximum over colours. For any partition in Definition 1.1,

0≤ui−∣Vi∣≤D,∣Vi∣=cinL+Or,q(1).(4)0\le u_i-|V_i|\le D,\qquad|V_i|=\frac{c_i n}{L}+O_{r,q}(1). \tag*{(4)}

The first assertion follows because the nonnegative capacity deficits sum to DD; the second follows from m=n/L+Or,q(1)m=n/L+O_{r,q}(1).

The two results

For two colourings χ,ψ\chi,\psi on the same vertex set VV, define

dist⁡(χ,ψ)=∣{e∈(Vr):χ(e)≠ψ(e)}∣,dist⁡(χ,Er,q(V))=min⁡ψ∈Er,q(V)dist⁡(χ,ψ).\operatorname{dist}(\chi,\psi)=\left|\left\{e\in\binom{V}{r}:\chi(e)\ne\psi(e)\right\}\right|,\qquad \operatorname{dist}(\chi,\mathcal{E}_{r,q}(V))=\min_{\psi\in\mathcal{E}_{r,q}(V)}\operatorname{dist}(\chi,\psi).

Theorem 1.2 (Edge-edit stability). For every ε>0\varepsilon>0, there are μ=μ(r,q,ε)>0\mu=\mu(r,q,\varepsilon)>0 and n0=n0(r,q,ε)n_0=n_0(r,q,\varepsilon) such that every colouring χ:(Vr)→[q]\chi:\binom{V}{r}\to[q] with n≥n0n\ge n_0 and

ν(Hi)≤(1+μ)nL(i∈[q])\nu(H_i)\le(1+\mu)\frac{n}{L}\qquad(i\in[q])

satisfies dist⁡(χ,Er,q(V))≤εnr\operatorname{dist}(\chi,\mathcal{E}_{r,q}(V))\le\varepsilon n^r.

Equivalently, for a sequence with n→∞n\to\infty,

max⁡iν(Hi)≤n/L+o(n)⟹dist⁡(χ,Er,q(V))=o(nr).\max_i\nu(H_i)\le n/L+o(n)\quad\Longrightarrow\quad\operatorname{dist}(\chi,\mathcal{E}_{r,q}(V))=o(n^r).

The stability theorem permits o(nr)o(n^r) exceptional edges. Our second result describes exactly which exceptions are possible when max⁡iν(Hi)=k\max_i\nu(H_i)=k. The quantity DD is the total unused capacity of a threshold partition, and the integers sis_i below distribute this unused capacity among the colours.

Theorem 1.3 (Exact normal form). There is nex=nex(r,q)n_{\mathrm{ex}}=n_{\mathrm{ex}}(r,q) such that, for every n≥nexn\ge n_{\mathrm{ex}}, a colouring χ\chi is extremal if and only if there are c∈Cr,qc\in\mathcal{C}_{r,q}, nonnegative integers s1,…,sqs_1,\ldots,s_q, and a partition V=W1⊔⋯⊔WqV=W_1\sqcup\cdots\sqcup W_q with

∣Wi∣=cim−1−si,∑isi=D,(5)|W_i|=c_i m-1-s_i,\qquad\sum_i s_i=D, \tag*{(5)}

such that, for each i∈[q]i\in[q], the family of violating edges

Fi={e∈(Vr):χ(e)=i, ∣e∩Wi∣<ci}\mathcal{F}_i=\{e\in\binom{V}{r}:\chi(e)=i,\ |e\cap W_i|<c_i\}

satisfies

∑e∈M(ci−∣e∩Wi∣)≤sifor every matching M⊆Fi.(6)\sum_{e\in M}(c_i-|e\cap W_i|)\le s_i\qquad\text{for every matching }M\subseteq\mathcal{F}_i. \tag*{(6)}

For colour ii, it suffices to check matchings in Fi\mathcal{F}_i with at most si+1≤Ls_i+1\le L edges. The sufficiency holds for every n≥rn\ge r for which the stated partition exists.

The positive integer δi(e)=ci−∣e∩Wi∣\delta_i(e)=c_i-|e\cap W_i| is the deficit of a violating colour-ii 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 nn; 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 rr-uniform family with prescribed matching number, whereas here all colour classes partition (Vr)\binom{V}{r} 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 rr-graph on a restricted vertex set, correspond to the endpoint conditions ci=1c_i=1 and ci=rc_i=r 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 ei/cie_i/c_i, with proportions ci/Lc_i/L. 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 o(nr−1)o(n^{r-1}). 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 r,qr,q. No explicit value of nex(r,q)n_{\mathrm{ex}}(r,q) is supplied.

We write 1=(1,…,1)\mathbf{1}=(1,\ldots,1) and ei\mathbf{e}_i for the iith coordinate vector. The support of a probability measure is its closed topological support. All asymptotic statements keep r,qr,q fixed. A partition may have empty parts unless nonemptiness is explicitly required. For a partition A1,…,AqA_1,\ldots,A_q and an edge ee, the vector (∣e∩A1∣,…,∣e∩Aq∣)(|e\cap A_1|,\ldots,|e\cap A_q|) 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 α>0\alpha>0 there is δ>0\delta>0 such that the following holds. Let tt be a positive integer and let z1,…,zt∈[0,1]qz_1,\ldots,z_t\in[0,1]^q satisfy

1t∑v=1tzv(i)≤1L+δ(i∈[q]).(7)\frac{1}{t}\sum_{v=1}^{t}z_v^{(i)}\le\frac{1}{L}+\delta\qquad(i\in[q]). \tag*{(7)}

For independent uniform indices v1,…,vr∈[t]v_1,\ldots,v_r\in[t], sampled with replacement, suppose that

P(max⁡i∑a=1rzva(i)<1)≤δ.(8)\mathbb{P}\left(\max_i\sum_{a=1}^{r}z_{v_a}^{(i)}<1\right)\le\delta. \tag*{(8)}

Put κ=1/(4r2)\kappa=1/(4r^2). There is c∈Cr,qc\in\mathbb{C}_{r,q} such that the sets Ii={v:∥zv−ei/ci∥∞<κ}I_i=\{v:\lVert z_v-\mathbf{e}_i/c_i\rVert_\infty<\kappa\} (i=1,…,qi=1,\ldots,q) and I0=[t]∖⋃i=1qIiI_0=[t]\setminus\bigcup_{i=1}^{q}I_i form a partition of [t][t] and satisfy

∣∣Ii∣t−ciL∣≤α(i∈[q]),∣I0∣≤αt.(9)\left|\frac{|I_i|}{t}-\frac{c_i}{L}\right|\le\alpha\quad(i\in[q]),\qquad|I_0|\le\alpha t. \tag*{(9)}

Proof. Suppose the lemma fails for some α>0\alpha>0. For each positive integer hh, take a counterexample with δ=1/h\delta=1/h and form its empirical measure σh=th−1∑v=1thδzh,v\sigma_h=t_h^{-1}\sum_{v=1}^{t_h}\delta_{z_{h,v}}, where δz\delta_z denotes the unit point mass at zz. 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 σh⇒σ\sigma_h\Rightarrow\sigma along such a subsequence and S=supp⁡σS=\operatorname{supp}\sigma.

Step 1: an exact covering problem on the support. Coordinate functions are continuous, so (2.1) implies

∫zi dσ(z)≤1/L(i∈[q]).(10)\int z_i\,\mathrm{d}\sigma(z)\le1/L\qquad(i\in[q]). \tag*{(10)}

We claim that, for all z(1),…,z(r)∈Sz^{(1)},\ldots,z^{(r)}\in S, including repetitions,

max⁡i∑a=1rzi(a)≥1.(11)\max_i\sum_{a=1}^{r}z_i^{(a)}\ge1. \tag*{(11)}

If this failed, continuity would give relative open neighbourhoods UaU_a of z(a)z^{(a)} whose entire Cartesian product violates the inequality. Each σ(Ua)>0\sigma(U_a)>0 because z(a)∈Sz^{(a)}\in S. The Portmanteau theorem [4] gives lim inf⁡hσh(Ua)≥σ(Ua)>0\liminf_h \sigma_h(U_a)\ge\sigma(U_a)>0. Independent sampling would therefore violate the inequality with probability at least ∏aσh(Ua)\prod_a\sigma_h(U_a), 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 C=conv⁡SC=\operatorname{conv}S. Since SS is compact and the ambient space is finite-dimensional, CC is compact. Choose u∈Cu\in C minimizing max⁡iui\max_i u_i. The barycentre ∫z dσ(z)\int z\,\mathrm{d}\sigma(z) belongs to CC, since CC is closed and convex and contains the support of σ\sigma. Thus for each i∈[q]i\in[q], we have ui≤1/Lu_i\le1/L.

If CC has affine dimension at most q−1q-1, Carathéodory’s theorem [19] represents uu using at most qq points of SS. If CC has dimension qq, then uu is on its boundary: otherwise u−ε1∈Cu-\varepsilon\mathbf{1}\in C for small ε>0\varepsilon>0, contrary to minimality. Take a supporting hyperplane through uu, using the supporting-hyperplane theorem [19]. In any finite convex representation of uu by points of SS, every point with a positive coefficient lies in that hyperplane, because all points of CC lie on one side. Carathéodory’s theorem in this face again uses at most qq points. Thus, omitting zero coefficients, we have u=∑j=1pλjwju=\sum_{j=1}^{p}\lambda_jw_j, p≤qp\le q, wj∈Sw_j\in S, λj>0\lambda_j>0, and ∑jλj=1\sum_j\lambda_j=1.

Set bj=⌈Lλj⌉−1b_j=\lceil L\lambda_j\rceil-1, a nonnegative integer strictly smaller than LλjL\lambda_j. If ∑jbj≥r\sum_j b_j\ge r, choose integers 0≤aj≤bj0\le a_j\le b_j with ∑jaj=r\sum_j a_j=r. Apply (2.5) to aja_j copies of each wjw_j. For some coordinate ℓ\ell, 1≤∑jajwj,ℓ<∑jLλjwj,ℓ=Luℓ≤11\le\sum_j a_jw_{j,\ell}<\sum_jL\lambda_jw_{j,\ell}=Lu_\ell\le1, a contradiction. The middle inequality is strict because every aj<Lλja_j<L\lambda_j, all coordinates are nonnegative, and the first sum has a positive term. Therefore r−1≥∑jbj=∑j⌈Lλj⌉−p≥L−p≥L−q=r−1r-1\ge\sum_jb_j=\sum_j\lceil L\lambda_j\rceil-p\ge L-p\ge L-q=r-1. Equality holds throughout. Hence p=qp=q and ∑j⌈Lλj⌉=∑jLλj\sum_j\lceil L\lambda_j\rceil=\sum_jL\lambda_j, so every cj:=Lλjc_j:=L\lambda_j is a positive integer. Their sum is LL.

Step 3: identify the support and its masses. For each jj, the profile c−1+ejc-\mathbf{1}+e_j is nonnegative and has sum rr. By (2.5), some coordinate ℓj\ell_j satisfies 1≤Luℓj−∑a≠jwa,ℓj≤11\le Lu_{\ell_j}-\sum_{a\ne j}w_{a,\ell_j}\le1. Equality throughout gives Luℓj=1Lu_{\ell_j}=1 and wa,ℓj=0w_{a,\ell_j}=0 for a≠ja\ne j. Since Luℓj=∑acawa,ℓjLu_{\ell_j}=\sum_ac_aw_{a,\ell_j}, it also gives cjwj,ℓj=1c_jw_{j,\ell_j}=1. The coordinates ℓj\ell_j are all distinct: if ℓj=ℓa\ell_j=\ell_a with j≠aj\ne a, the latter equality for jj contradicts the zero forced by the equality for aa. Since j↦ℓjj\mapsto\ell_j is a permutation of [q][q], relabel the selected support points and their associated integers so that ℓj=j\ell_j=j. All qq coordinates have been used, and therefore for every j∈[q]j\in[q], we have wj=ej/cjw_j=e_j/c_j.

For any z∈Sz\in S, apply (2.5) to the following rr support points: cj−1c_j-1 copies of ej/cje_j/c_j for each jj. In coordinate ii, their sum is zi+(ci−1)/ciz_i+(c_i-1)/c_i. Thus cizi≥1c_iz_i\ge1 for some ii. Consequently

g(z):=∑icizi≥1(z∈S),∫g dσ≤∑ici/L=1g(z):=\sum_i c_i z_i\ge1\quad(z\in S),\qquad\int g\,\mathrm{d}\sigma\le\sum_i c_i/L=1

by (2.4). Thus g=1g=1 on SS: a support point with g>1g>1 would, by continuity, have a positive-measure neighbourhood on which gg exceeds one by a fixed amount. Combining g(z)=1g(z)=1 with cizi≥1c_iz_i\ge1 and nonnegativity gives z=ei/ciz=e_i/c_i. If pip_i is the mass at ei/cie_i/c_i, then pi/ci≤1/Lp_i/c_i\le1/L by (2.4). Since ∑ipi=1=∑ici/L\sum_i p_i=1=\sum_i c_i/L, all these bounds are equalities:

σ=∑iciLδei/ci.(12)\sigma=\sum_i\frac{c_i}{L}\delta_{e_i/c_i}. \tag*{(12)}

Finally, the open balls of radius κ\kappa around the axis points are disjoint: their centres have ℓ∞\ell_\infty-distance at least 1/r>2κ1/r>2\kappa. Their boundaries contain no atom of (2.6). Weak convergence gives ∣Ii∣/th→ci/L|I_i|/t_h\to c_i/L and ∣I0∣/th→0|I_0|/t_h\to0. For large hh this is (2.3), contradicting the choice of the counterexamples. □\square

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 X1,…,XrX_1,\ldots,X_r, let dH(X1,…,Xr)d_H(X_1,\ldots,X_r) be the number of edges of HH meeting each set once, divided by ∣X1∣⋯∣Xr∣|X_1|\cdots|X_r|. The tuple is η\eta-regular in HH if

∣dH(Y1,…,Yr)−dH(X1,…,Xr)∣≤η\left|d_H(Y_1,\ldots,Y_r)-d_H(X_1,\ldots,X_r)\right|\le\eta

whenever Ya⊂XaY_a\subset X_a and ∣Ya∣≥η∣Xa∣|Y_a|\ge\eta|X_a| for all aa. 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 p=1p=1, 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 η>0\eta>0 and integer t0≥rt_0\ge r, there are integers T,NT,N such that any rr-uniform hypergraphs H1,…,HqH_1,\ldots,H_q on a common vertex set of size n≥Nn\ge N admit an equitable partition X1,…,XtX_1,\ldots,X_t, with t0≤t≤Tt_0\le t\le T, such that, for every i∈[q]i\in[q], at most η(tr)\eta\binom{t}{r} of the unordered rr-tuples of distinct parts fail to be η\eta-regular in HiH_i.

Call a tuple jointly regular if it is regular in every colour. At most qη(tr)q\eta\binom{t}{r} tuples are not jointly regular. Fix 0<η<d<1/q0<\eta<d<1/q. Given an equitable partition of a colouring, define an rr-graph JiJ_i on [t][t] for each i∈[q]i\in[q] by

Q∈E(Ji)⟺{Q∈([t]r) is jointly regular,dHi((Xv)v∈Q)≥d.(13)Q\in E(J_i)\Longleftrightarrow \begin{cases} Q\in\binom{[t]}{r}\text{ is jointly regular},\\ d_{H_i}((X_v)_{v\in Q})\ge d. \end{cases} \tag*{(13)}

All colours of density at least dd are retained; the JiJ_i may overlap. This is important: an edge of density at least dd in colour ii must be retained in JiJ_i, even if it also belongs to another JjJ_j. Since the colour densities sum to one, every jointly regular tuple belongs to at least one JiJ_i.

A fractional matching in an rr-graph JJ 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

ν∗(J)=max⁡{∑Q∈E(J)xQ:xQ≥0, ∑Q∋vxQ≤1 for all v}=min⁡{∑v∈V(J)zv:0≤zv≤1, ∑v∈Qzv≥1 for all Q∈E(J)}.(14)\begin{aligned} \nu^*(J)=\max\left\{\sum_{Q\in E(J)}x_Q:x_Q\ge0,\ \sum_{Q\ni v}x_Q\le1\text{ for all }v\right\} \\ &=\min\left\{\sum_{v\in V(J)}z_v:0\le z_v\le1,\ \sum_{v\in Q}z_v\ge1\text{ for all }Q\in E(J)\right\}. \tag*{(14)} \end{aligned}

The upper bounds zv≤1z_v\le1 cause no loss: truncating a larger coordinate at one preserves every cover constraint.

Lemma 3.2 (Fractional matching lift). Let JiJ_i be defined by (13), with 0<η<d<1/q0<\eta<d<1/q. Suppose the clusters have size bb or b+1b+1, where bb is a positive integer. Then

ν(Hi)≥(1−2η)bν∗(Ji)−(tr)(i∈[q]).\nu(H_i)\ge(1-2\eta)b\nu^*(J_i)-\binom{t}{r}\qquad(i\in[q]).

Proof. Take an optimal fractional matching (xQ)(x_Q) in JiJ_i. For each QQ, set a demand of NQ=⌊(1−2η)bxQ⌋N_Q=\lfloor(1-2\eta)bx_Q\rfloor colour-ii 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 XvX_v is at most

∑Q∋vNQ≤(1−2η)b∑Q∋vxQ≤(1−2η)b.\sum_{Q\ni v}N_Q\le(1-2\eta)b\sum_{Q\ni v}x_Q\le(1-2\eta)b.

At every stage each cluster has at least 2ηb2\eta b unused vertices. Since b≥1b\ge1 gives 2ηb≥η(b+1)2\eta b\ge\eta(b+1), each unused set is large enough for regularity. For the current tuple the colour-ii density on its unused sets is at least d−η>0d-\eta>0, so the next edge exists. The resulting matching has size

∑QNQ≥(1−2η)b∑QxQ−∣E(Ji)∣≥(1−2η)bν∗(Ji)−(tr).\sum_Q N_Q \ge(1-2\eta)b\sum_Q x_Q-|E(J_i)|\ge(1-2\eta)b\nu^*(J_i)-\binom{t}{r}.

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 c∈Cr,qc\in\mathcal{C}_{r,q} and V=A1⊔⋯⊔AqV=A_1\sqcup\cdots\sqcup A_q. Suppose at most BB edges of χ\chi violate χ(e)=i⇒∣e∩Ai∣≥ci\chi(e)=i\Rightarrow|e\cap A_i|\ge c_i. Put E=∑imax⁡{0,∣Ai∣−(cim−1)}E=\sum_i\max\{0,|A_i|-(c_i m-1)\}. Then

dist⁡(χ,Er,q(V))≤B+E(n−1r−1).(15)\operatorname{dist}(\chi,\mathcal{E}_{r,q}(V))\le B+E\binom{n-1}{r-1}. \tag*{(15)}

Proof. The capacities sum to n+Dn+D, so the total unused capacity in underfull parts is E+D≥EE+D\ge E. Move exactly EE 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 BB 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 E(n−1r−1)E\binom{n-1}{r-1} edges meet a moved vertex, proving (3.3).

Proof of the stability theorem

Proof of Theorem 1.2. We may assume 0<ε≤10<\varepsilon\le1. Throughout this proof, the parameters in (1.1) are computed from the current order nn.

Step 1: parameter selection. Set α=ε/[4(4q+3)]\alpha=\varepsilon/[4(4q+3)] and obtain δ>0\delta>0 from Lemma 2.1; decrease it so that δ≤1/L\delta\le1/L. Choose 0<d≤min⁡{12q,ε2r+3q}0<d\le\min\left\{\frac{1}{2q},\frac{\varepsilon}{2^{r+3}q}\right\}. Next choose η,μ>0\eta,\mu>0 so that η<d\eta<d, qη≤δ/2q\eta\le\delta/2, and 1+μL(1−2η)<1L+δ2\frac{1+\mu}{L(1-2\eta)}<\frac{1}{L}+\frac{\delta}{2}. This is possible because the last fraction tends to 1/L1/L as η,μ→0\eta,\mu\to0. Take an integer t0≥max⁡{r,8ε,2(r)ε}t_0\ge\max\left\{r,\frac{8}{\varepsilon},\frac{2^{(r)}}{\varepsilon}\right\}, and apply Lemma 3.1 to obtain T,NT,N. Finally choose n0≥Nn_0\ge N so large that, for every n≥n0n\ge n_0, T≤αnT\le\alpha n, q≤αnq\le\alpha n, and

(1+μ)/L+Tr/n(1−2η)(1−T/n)≤1L+δ.\frac{(1+\mu)/L+T^r/n}{(1-2\eta)(1-T/n)}\le\frac{1}{L}+\delta.

The last requirement is possible because its left side tends to (1+μ)/(L(1−2η))(1+\mu)/(L(1-2\eta)), which is less than 1/L+δ/21/L+\delta/2. Thus all constants, including TT, have been fixed before n0n_0.

Step 2: obtain the threshold vector from cover weights. Let χ\chi satisfy the theorem’s assumptions, and take a regular partition with t0≤t≤Tt_0\le t\le T and cluster sizes bb or b+1b+1, where b=⌊n/t⌋b=\lfloor n/t\rfloor. Define all the JiJ_i by (3.1) and choose optimal covers zv(i)∈[0,1]z_v^{(i)}\in[0,1]. By (3.2) and Lemma 3.2,

1t∑vzv(i)=ν∗(Ji)t≤(1+μ)n/L+(tr)(1−2η)bt≤(1+μ)/L+Tr/n(1−2η)(1−T/n)≤1L+δ.\frac{1}{t}\sum_v z_v^{(i)}=\frac{\nu^*(J_i)}{t}\le\frac{(1+\mu)n/L+\binom{t}{r}}{(1-2\eta)bt}\le\frac{(1+\mu)/L+T^r/n}{(1-2\eta)(1-T/n)}\le\frac{1}{L}+\delta.

Here bt≥n−t≥n−Tbt\ge n-t\ge n-T. For independent uniform indices v1,…,vrv_1,\ldots,v_r, the probability of a repetition is at most (r2)/t\binom{r}{2}/t. Conditional on being distinct, their underlying rr-set is uniform. If it is jointly regular, it belongs to some JiJ_i and hence has cover sum at least one in that coordinate. Thus, for zv=(zv(1),…,zv(q))z_v=(z_v^{(1)},\ldots,z_v^{(q)}),

P(max⁡i∑vzv(i)<1)≤qη+(r2)t0≤δ.\mathbb{P}\left(\max_i\sum_v z_v^{(i)}<1\right)\le q\eta+\frac{\binom{r}{2}}{t_0}\le\delta.

Lemma 2.1 now gives c∈Cr,qc\in\mathcal{C}_{r,q} and I0,I1,…,IqI_0,I_1,\ldots,I_q satisfying (2.3).

Let Ai0=⋃v∈IiXvA_i^0=\bigcup_{v\in I_i}X_v and Z=⋃v∈I0XvZ=\bigcup_{v\in I_0}X_v. Equitability gives ∣Z∣≤αt(b+1)≤2αn|Z|\le\alpha t(b+1)\le2\alpha n, and ∣∣Ai0∣−cinL∣≤αn+t≤2αn\left||A_i^0|-\frac{c_i n}{L}\right|\le\alpha n+t\le2\alpha n. For the second bound, replacing each cluster size by n/tn/t changes the sum over IiI_i by at most tt. Assign ZZ arbitrarily to the parts, obtaining a partition A1,…,AqA_1,\ldots,A_q of VV with

∣∣Ai∣−cinL∣≤4αn.(16)\left||A_i|-\frac{c_i n}{L}\right|\le4\alpha n. \tag*{(16)}

Step 3: bound every violation of the threshold rule. Consider a jointly regular tuple QQ of clusters in I1∪⋯∪IqI_1 \cup\cdots\cup I_q, and put ai=∣Q∩Ii∣a_i = |Q \cap I_i|. By the definition of the clusters IjI_j, each zv(i)z_v^{(i)} differs from 1/ci1/c_i by less than κ\kappa when v∈Iiv \in I_i, and is less than κ\kappa otherwise. Hence

∑v∈Qzv(i)≤aici+rκ.\sum_{v \in Q} z_v^{(i)} \le\frac{a_i}{c_i} + r\kappa.

If ai<cia_i < c_i, then, since ci≤rc_i \le r,

∑v∈Qzv(i)≤1−1ci+rκ≤1−1r+14r<1.\sum_{v \in Q} z_v^{(i)} \le1 - \frac{1}{c_i} + r\kappa\le1 - \frac{1}{r} + \frac{1}{4r} < 1.

The cover constraint rules out Q∈JiQ \in\mathcal{J}_i. Joint regularity and (3.1) therefore imply that its colour-ii density is less than dd. Summing over ineligible colours, the wrong-colour density on this tuple is at most qdqd.

Every threshold violation either meets ZZ, 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 BB consequently satisfies

B≤∣Z∣(n−1r−1)+∑v=1t(∣Xv∣2)(n−2r−2)+q(η+d)(tr)(b+1)r.B \le|Z| \binom{n-1}{r-1} + \sum_{v=1}^{t} \binom{|X_v|}{2} \binom{n-2}{r-2} + q(\eta+d)\binom{t}{r}(b+1)^r.

Here b+1≤2n/tb+1 \le2n/t and ∑v=1t(∣Xv∣2)≤t(b+1)2/2≤2n2/t\sum_{v=1}^{t} \binom{|X_v|}{2} \le t(b+1)^2/2 \le2n^2/t. Thus the middle term is at most 2nr/t2n^r/t, and the last term is at most 2rq(η+d)nr2^r q(\eta+d)n^r. Therefore

Bnr≤2α+2t0+2rq(η+d).\frac{B}{n^r} \le2\alpha+ \frac{2}{t_0} + 2^r q(\eta+d).

Finally, m=(n+q+D)/L≥n/Lm = (n+q+D)/L \ge n/L, so ui=cim−1≥cin/L−1u_i = c_i m - 1 \ge c_i n/L - 1. (16) gives

E=∑imax⁡{0,∣Ai∣−ui}≤q(4αn+1)≤(4q+1)αn.E = \sum_i \max\{0, |A_i| - u_i\} \le q(4\alpha n + 1) \le(4q+1)\alpha n.

Applying Lemma 3.3 and (n−1r−1)≤nr−1\binom{n-1}{r-1} \le n^{r-1}, we obtain

dist⁡(χ,Er,q(V))nr≤(4q+3)α+2t0+2rq(η+d)≤3ε4<ε.\frac{\operatorname{dist}(\chi,\mathcal{E}_{r,q}(V))}{n^r} \le(4q+3)\alpha+ \frac{2}{t_0} + 2^r q(\eta+d) \le\frac{3\varepsilon}{4} < \varepsilon.

The three terms are each at most ε/4\varepsilon/4 by the choices of α\alpha, t0t_0, dd and η<d\eta< d. 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 NN were a colour-ii matching with mm edges, then

∣Wi∣≥∑e∈N∩Fi∣e∩Wi∣≥cim−∑e∈N∩Fiδi(e)≥cim−si=∣Wi∣+1,|W_i| \ge\sum_{e \in N \cap F_i} |e \cap W_i| \ge c_i m - \sum_{e \in N \cap F_i} \delta_i(e) \ge c_i m - s_i = |W_i| + 1,

a contradiction. Thus every colour has matching number at most m−1=km-1 = k, 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 si+1s_i+1 edges, any si+1s_i+1 of them would already have total deficit at least si+1s_i+1, since the deficits are positive integers. This would contradict minimality. Thus a violation has a witness of at most si+1≤D+1≤Ls_i+1 \le D+1 \le L edges. □

A profile switching lemma

Let a=(a1,…,aq)a = (a_1,\ldots,a_q) be a nonnegative integer vector of sum rr, and let hh be a positive integer. For disjoint sets UjU_j of sizes ajha_jh, write

K(a;U1,…,Uq)={e⊆⋃jUj:∣e∩Uj∣=aj for all j}.\mathcal{K}(a;U_1,\ldots,U_q) = \{e \subseteq\bigcup_j U_j : |e \cap U_j| = a_j \text{ for all } j\}.

For an edge family BB, let dB(v)=∣{e∈B:v∈e}∣d_B(v) = |\{e \in B : v \in e\}| and Δ(B)=max⁡vdB(v)\Delta(B) = \max_v d_B(v). 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 BB bad and the other edges good.

Lemma 4.1 (Profile switching). Allow Uj=∅U_j=\varnothing when aj=0a_j=0. If h≥rh\ge r and K(a;U1,…,Uq)⊆\mathcal{K}(a;U_1,\ldots,U_q)\subseteq B\mathcal{B} satisfies

rΔ(B)<(h−1)r−1:=(h−1)(h−2)⋯(h−r+1),(17)r\Delta(\mathcal{B})<(h-1)_{r-1}:=(h-1)(h-2)\cdots(h-r+1), \tag*{(17)}

then K(a;U1,…,Uq)∖B\mathcal{K}(a;U_1,\ldots,U_q)\setminus\mathcal{B} contains a perfect matching of size hh. In particular, Δ(B)=o(hr−1)\Delta(\mathcal{B})=o(h^{r-1}) suffices as h→∞h\to\infty.

Proof. For each jj, write UjU_j as the disjoint union of hh labelled blocks of size aja_j (all empty if aj=0a_j=0). Unite blocks with the same label. This gives a perfect matching in the complete profile hypergraph. Choose one, MM, with as few bad edges as possible, and suppose e0∈M∩Be_0\in M\cap\mathcal{B}.

Divide the positions 0,…,r−10,\ldots,r-1 into groups of sizes a1,…,aqa_1,\ldots,a_q. Label the vertices of every edge of MM by these positions, so that the same positions always belong to the same part UjU_j. Fix all labels before making the following choices.

Choose ordered distinct edges e1,…,er−1∈M∖{e0}e_1,\ldots,e_{r-1}\in M\setminus\{e_0\}. For 0≤a,b<r0\le a,b<r, let xa,bx_{a,b} be the vertex in position bb of eae_a. Put

fs={xa,b:a+b≡s(modr)},0≤s<r.f_s=\{x_{a,b}:a+b\equiv s\pmod r\},\qquad0\le s<r.

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 fsf_s contains the fixed vertex x0,sx_{0,s}.

For a fixed ss, any prescribed edge arising as fsf_s determines at most one ordered tuple (e1,…,er−1)(e_1,\ldots,e_{r-1}) of old edges. Each of its vertices identifies its old matching edge and its fixed position bb, and hence that edge’s row a≡s−b(modr)a\equiv s-b\pmod r. At most dB(x0,s)d_{\mathcal{B}}(x_{0,s}) choices therefore make fsf_s bad. At most rΔ(B)r\Delta(\mathcal{B}) choices make any new edge bad, whereas there are (h−1)r−1(h-1)_{r-1} 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 MM, write V(M)=⋃e∈MeV(M)=\bigcup_{e\in M}e, with V(∅)=∅V(\varnothing)=\varnothing. 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 WW, then the remaining vertices of WW allow it to be extended to a matching of size mm.

Lemma 4.2 (Bounded matching completion). Fix c∈Cr,q\mathbf{c}\in\mathcal{C}_{r,q}, i∈[q]i\in[q], an integer B≥0B\ge0, and γ>0\gamma>0. Consider a sequence of qq-colourings of complete rr-graphs, with an integer parameter m→∞m\to\infty and vertex partitions

V=A1∪˙⋯∪˙Aq∪˙X,∣Aj∣=cjm+o(m),∣X∣=o(m).V=A_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}A_q\mathbin{\dot\cup}X,\qquad|A_j|=c_jm+o(m),\qquad|X|=o(m).

Let p(i)=c−1+ei\mathbf{p}^{(i)}=\mathbf{c}-\mathbf{1}+\mathbf{e}_i. Suppose the family of edges in the cores A1,…,AqA_1,\ldots,A_q with profile p(i)\mathbf{p}^{(i)} that are not coloured ii has maximum degree o(mr−1)o(m^{r-1}). Let Y⊆XY\subseteq X and put W=Ai∪˙YW=A_i\mathbin{\dot\cup}Y. Assume each x∈Yx\in Y belongs to at least γmr−1\gamma m^{r-1} colour- ii edges {x}∪S\{x\}\cup S with

S⊆A1∪⋯∪Aq,∣S∩Aj∣=cj−1(j∈[q]).(18)S\subseteq A_1\cup\cdots\cup A_q,\qquad|S\cap A_j|=c_j-1\quad(j\in[q]). \tag*{(18)}

Suppose ν(Hi)<m\nu(H_i)<m for every member of the sequence. Then, for all sufficiently large members of the sequence, every colour- ii matching MM with ∣M∣≤B|M|\le B, including the empty matching, satisfies

ci∣M∣−∣V(M)∩W∣≤cim−∣W∣−1.(19)c_i|M|-|V(M)\cap W|\le c_im-|W|-1. \tag*{(19)}

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 MM is violating relative to WW.

Proof. Fix a member of the sequence and a colour-ii matching MM with ∣M∣≤B|M|\le B. Set

ℓ=∣M∣,aj=∣V(M)∩Aj∣,b=∣V(M)∩Y∣,t=∣Y∣−b.\ell=|M|,\qquad a_j=|V(M)\cap A_j|,\qquad b=|V(M)\cap Y|,\qquad t=|Y|-b.

Then ℓ≤B\ell\le B, aj≤rBa_j \le rB and t=o(m)t = o(m). We work with a sufficiently large member of the sequence; the estimates below will be uniform over all such MM. If (19) fails, integrality gives

ciℓ−ai−b≥cim−∣W∣.(20)c_i\ell-a_i-b \ge c_i m-|W|. \tag*{(20)}

For each x∈Y∖V(M)x \in Y \setminus V(M), choose a colour-ii edge {x}∪Sx\{x\} \cup S_x satisfying (18), disjoint from MM and the previously chosen edges. This is possible greedily. At most rB+(r−1)∣Y∣=o(m)rB+(r-1)|Y|=o(m) core vertices are forbidden. Each forbidden core vertex excludes at most

∣V∣r−2r−2=Or,q(mr−2)\frac{|V|^{r-2}}{r-2}=O_{r,q}(m^{r-2})

candidates through xx, since ∣V∣=Lm+o(m)|V|=Lm+o(m). Thus at most o(mr−1)o(m^{r-1}) of the at least γmr−1\gamma m^{r-1} colour-ii candidates are excluded. The noncore vertex of each edge is its own distinct xx, outside V(M)V(M).

After these tt choices, we seek h=m−ℓ−t=(1−o(1))mh=m-\ell-t=(1-o(1))m further colour-ii edges of profile p(i)p^{(i)}. In the iith core, the number of remaining vertices minus the number required is

∣Ai∣−ai−t(ci−1)−cih=ciℓ−ai+t+∣Ai∣−cim=ciℓ−ai−b+∣W∣−cim≥0,\begin{aligned} |A_i|-a_i-t(c_i-1)-c_i h=c_i\ell-a_i+t+|A_i|-c_i m \\ &=c_i\ell-a_i-b+|W|-c_i m\ge0, \end{aligned}

by (20). For j≠ij\ne i, the difference is

∣Aj∣−aj−t(cj−1)−(cj−1)h=∣Aj∣−(cj−1)m−aj+(cj−1)ℓ=m+o(m)>0.\begin{aligned} |A_j|-a_j-t(c_j-1)-(c_j-1)h=|A_j|-(c_j-1)m-a_j+(c_j-1)\ell\\ &=m+o(m)>0. \end{aligned}

For sufficiently large mm, we have h≥rh\ge r. Choose subsets of the remaining cores having exactly pj(i)hp_j^{(i)}h vertices in each AjA_j. The wrong-colour family on them still has maximum degree o(mr−1)=o(hr−1)o(m^{r-1})=o(h^{r-1}). Lemma 4.1 supplies hh disjoint colour-ii edges. Together with MM and the tt selected links, they form a matching of size ℓ+t+h=m\ell+t+h=m, a contradiction. The number of forbidden core vertices is bounded by rB+(r−1)∣Y∣rB+(r-1)|Y|, independently of the choice of MM. The switching bound also depends only on the given wrong-colour maximum degree and on h=m−O(B)−o(m)h=m-O(B)-o(m). Consequently, one sufficiently large index works simultaneously for all matchings with ∣M∣≤B|M|\le B. □

Necessity of the normal form

Proof of the necessity in Theorem 1.3. Suppose that there are counterexamples for arbitrarily large nn. Choose such a sequence with n→∞n\to\infty, and use k,m,Dk,m,D from (1). All asymptotic estimates below refer to this sequence.

Step 1: remove vertices with large error degree. Extremality gives max⁡iν(Hi)≤k=n/L+Or,q(1)\max_i \nu(H_i)\le k=n/L+O_{r,q}(1). The sequential form of Theorem 1.2 yields ψ∈Er,q(V)\psi\in\mathcal{E}_{r,q}(V) with

B={e:χ(e)≠ψ(e)},∣B∣=o(nr)=o(mr).\mathcal{B}=\{e:\chi(e)\ne\psi(e)\},\qquad|\mathcal{B}|=o(n^r)=o(m^r).

Let A1′,…,Aq′A'_1,\ldots,A'_q be a witnessing partition for ψ\psi. After passing to a subsequence, its vector c∈Cr,qc\in\mathcal{C}_{r,q} is fixed, because there are finitely many such vectors. By (4), ∣Aj′∣=cjm+Or,q(1)|A'_j|=c_jm+O_{r,q}(1).

Write β=∣B∣/mr=o(1)\beta=|\mathcal{B}|/m^r=o(1), put θ=β+m−1/2\theta=\sqrt{\beta}+m^{-1/2}, and let X={v:dB(v)>θmr−1}X=\{v:d_{\mathcal{B}}(v)>\theta m^{r-1}\} and Aj=Aj′∖XA_j=A'_j\setminus X. Since ∑vdB(v)=r∣B∣\sum_v d_{\mathcal{B}}(v)=r|\mathcal{B}|, we have ∣X∣≤rβθm=o(m)|X|\le\frac{r\beta}{\theta}m=o(m) and ∣Aj∣=cjm+o(m)|A_j|=c_jm+o(m). An edge in the cores with profile p(i)=c−1+eip^{(i)}=c-\mathbf{1}+e_i has only colour ii eligible in ψ\psi. Every such edge not coloured ii in χ\chi therefore belongs to B\mathcal{B}. Its wrong-colour family has maximum degree at most θmr−1=o(mr−1)\theta m^{r-1}=o(m^{r-1}).

Step 2: assign the exceptional vertices to colours. For x∈Xx\in X, the number of edges {x}∪S\{x\}\cup S with ∣S∩Aj∣=cj−1|S\cap A_j|=c_j-1 for every jj is

∏j=1q(∣Aj∣cj−1)=Θr,q(mr−1).\prod_{j=1}^{q}\binom{|A_j|}{c_j-1}=\Theta_{r,q}(m^{r-1}).

Here ∣Aj∣=cjm+o(m)|A_j|=c_jm+o(m) and ∑j(cj−1)=r−1\sum_j(c_j-1)=r-1. By the pigeonhole principle, one colour τ(x)\tau(x) occurs on at least γmr−1\gamma m^{r-1} of these edges, for a fixed γ>0\gamma>0 depending only on r,qr,q. Indeed, the leading coefficient of the product above is ∏jcjcj−1/(cj−1)!>0\prod_j c_j^{c_j-1}/(c_j-1)! > 0, with 0!=10! = 1; there are only finitely many possible vectors cc. Fix such a colour for each xx and put

Xi={x∈X:τ(x)=i},Wi=Ai⊔Xi.X_i = \{x \in X : \tau(x) = i\}, \qquad W_i = A_i \sqcup X_i.

These sets form a partition of VV.

Step 3: recover the capacities and deficit budgets. Apply Lemma 4.2 with B=LB = L, Y=XiY = X_i and W=WiW = W_i, for each ii. Its hypotheses follow from Steps 1–2 and ν(Hi)≤m−1\nu(H_i) \le m - 1. Since there are only qq colours, the conclusions hold simultaneously for all ii from some index onwards. Hence every colour-ii matching with at most LL edges obeys

ci∣M∣−∣V(M)∩Wi∣≤cim−∣Wi∣−1.(21)c_i|M| - |V(M) \cap W_i| \le c_i m - |W_i| - 1. \tag*{(21)}

Taking M=∅M = \varnothing defines nonnegative integers si=cim−∣Wi∣−1≥0s_i = c_i m - |W_i| - 1 \ge0. Because the WiW_i partition VV,

∣Wi∣=cim−1−si,∑isi=Lm−n−q=D.|W_i| = c_i m - 1 - s_i, \qquad\sum_i s_i = Lm - n - q = D.

For a matching MM of violating colour-ii edges, disjointness gives ∑e∈Mδi(e)=ci∣M∣−∣V(M)∩Wi∣\sum_{e \in M} \delta_i(e) = c_i|M| - |V(M) \cap W_i|. If it violated the budget sis_i, the bounded-witness argument at the start of this section would give a violating submatching with at most si+1≤D+1≤Ls_i + 1 \le D + 1 \le L 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 nex(r,q)n_{\mathrm{ex}}(r,q) and the necessity of the normal form. □\square

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. [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. [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. [3]I. Bárány, A short proof of Kneser’s conjecture, J. Combin. Theory Ser. A 25 (1978), 325–326.DOI
  4. [4]P. Billingsley, Convergence of Probability Measures, 2nd ed., Wiley Series in Probability and Statistics, John Wiley & Sons, New York, 1999.
  5. [5]F. R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 (1991), 241–252.
  6. [6]E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975), 252–256.DOI
  7. [7]P. Erdős, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95.
  8. [8]P. Frankl, Improved bounds for Erdős’ matching conjecture, J. Combin. Theory Ser. A 120 (2013), 1068–1072.DOI
  9. [9]P. Frankl and A. Kupavskii, Beyond the Erdős matching conjecture, European J. Combin. 95 (2021), Paper No. 103338.
  10. [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. [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. [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. [13]L. Gishboliner, M. Krivelevich and P. Michaeli, Color-biased Hamilton cycles in random graphs, Random Structures Algorithms 60 (2022), 289–307.DOI
  14. [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. [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. [16]L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), 319–324.DOI
  17. [17]L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, Amsterdam, 1986.
  18. [18]J. Matoušek, Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer, Berlin, 2003.
  19. [19]R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton University Press, Princeton, NJ, 1970.
  20. [20]A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24, Springer, Berlin, 2003.
  21. [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

Paper details

vlnc:W_g2d3uwnn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents