pith. sign in

arxiv: 2606.24863 · v1 · pith:AMW2GQHXnew · submitted 2026-06-23 · 🧮 math.CO

Structural Reductions for Monochromatic Matchings and Ramsey Tilings

Hong Liu , Maksim Turevskii , Lanchao Wang , Zhifei Yan This is my paper

Pith reviewed 2026-06-25 22:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph coloringsmonochromatic matchingsRamsey tilingsstructural reductionspseudo-random hypergraphslinear programstiling numbers
0
0 comments X

The pith

Every r-coloring of a sufficiently pseudo-random t-uniform hypergraph reduces with only o(n) loss in monochromatic matching size to a coloring of the complete hypergraph on a partitioned vertex set whose colors depend only on intersection p

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a structural reduction for r-edge-colorings of hypergraphs that nearly preserves the size of the largest monochromatic matching. It shows that any coloring of a sufficiently pseudo-random t-uniform hypergraph can be approximated by a coloring of the complete t-uniform hypergraph whose vertices are split into at most r parts and whose colors are determined solely by how edges intersect those parts. This framework yields asymptotic results on monochromatic matchings and tilings using only combinatorial arguments. It further establishes that the minimum size of a largest monochromatic H-tiling in any r-edge-coloring of the complete graph on n vertices equals (β + o(1))n, where β is the value of a finite collection of linear programs depending only on H and r.

Core claim

The central claim is that every r-edge-coloring of a sufficiently pseudo-random t-graph admits a reduction, losing only o(n) in the size of the largest monochromatic matching, to an r-edge-coloring of the complete t-uniform hypergraph whose vertex set is partitioned into at most r parts and whose edge colors depend only on intersection profiles with the parts. This reduction implies that the multicolour Ramsey tiling number Rt_r(H; K_n) equals (β_{r,H} + o(1))n, where β_{r,H} is the optimum of finitely many linear programs that depend only on the fixed graph H and the number of colors r.

What carries the argument

The structural reduction obtained by combining the hypergraph regularity lemma, LP duality, and convex-geometric compression, which converts an arbitrary pseudo-random coloring into an intersection-profile coloring on a bounded partition of the vertices.

If this is right

  • The asymptotic form of the theorem on minimum monochromatic matching size in complete hypergraphs admits a proof that does not rely on topology.
  • A transference principle holds that transfers the result from complete hypergraphs to sparse random hypergraphs.
  • Near-exact bounds hold for certain linear-uniformity cases of stable Kneser-type problems.
  • The multicolour Ramsey tiling problem on complete hosts has an effective asymptotic solution via linear programs.
  • Explicit values of the asymptotic constant β are obtained for connected non-bipartite graphs, balanced Hall-type bipartite graphs, complete bipartite graphs with three to five colors, and some non-Hall bipartite graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The reduction technique may extend to other multicolour problems involving matchings or tilings in hypergraphs where pseudo-randomness is present.
  • The linear-program formulation opens the possibility of algorithmic computation of the tiling constants for concrete small values of r and H.
  • The same compression approach could be tested on related problems in extremal set theory that currently rely on topological methods.

Load-bearing premise

The input hypergraph must be sufficiently pseudo-random for the regularity and compression steps to produce a reduction with only o(n) loss.

What would settle it

An r-edge-coloring of a pseudo-random t-uniform hypergraph in which every reduction to a partitioned profile coloring loses more than o(n) vertices from the largest monochromatic matching would disprove the main theorem.

Figures

Figures reproduced from arXiv: 2606.24863 by Hong Liu, Lanchao Wang, Maksim Turevskii, Zhifei Yan.

Figure 1
Figure 1. Figure 1: The structural pipeline: from coloured reduced hypergraphs to dual cluster weights Si , then to a compressed vector system Yi , and finally to a strip￾colouring template. 2.1. Dual weights from reduced matchings. Apply the multicolour weak hypergraph regularity lemma to an r-edge-coloured pseudo-random t-graph. This gives an equipartition into M = Or,t,ε(1) clusters. For each colour ℓ, let Xℓ be the family… view at source ↗
Figure 2
Figure 2. Figure 2: Extremal 3-colourings for Lemma 6.6. Lemma 6.7. Let b ⩾ a ⩾ 1 and N1 ⩾ N2. The complete bipartite graph KN1,N2 contains a Ka,b-tiling of size at least min  N1 + N2 a + b , N2 a  − Oa,b(1). Proof. If a = b, the assertion follows by greedily taking ⌊N2/a⌋ copies. Assume b > a. If aN1 > bN2, orient every copy with b vertices in the first class and a in the second; this gives ⌊N2/a⌋ copies. Suppose instead t… view at source ↗
Figure 3
Figure 3. Figure 3: The D2,3 construction. For comparison, the complete bipartite graph K3,4, which has the same bipartition sizes, has three-colour constant 1/13 by Theorem 6.5. Thus the tiling constant is not determined by the 29 [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Extremal four-colour strip templates for Ka,b-tilings. For Λ1, colour 1 occurs only inside the first part, while every edge of colour j ∈ {2, 3, 4} meets the j-th part. For Λ2, each of colours 1, 2, 3 is supported on two of the three large parts, while every colour-4 edge meets the fourth part. For Λ3, every colour is supported on parts of total normalized size at most 3/5. These observations give the thre… view at source ↗
Figure 5
Figure 5. Figure 5: Extremal five-colour strip templates for Ka,b-tilings. The five-colour optimization has one additional regime and its proof uses Theorem 6.10 recursively inside a four-part subtemplate. Since the resulting case analysis is substantially longer, we defer it to Appendix A. These formulas suggest that, although Theorem 1.7 gives a finite optimization for every fixed number of colours, extracting a uniform clo… view at source ↗
read the original abstract

The Alon--Frankl--Lov\'asz theorem determines the chromatic number of Kneser hypergraphs; equivalently, it gives the sharp minimum size of a monochromatic matching in every \(r\)-edge-colouring of the complete \(t\)-uniform hypergraph. The known proofs of the exact theorem are topological. We develop a topology-free structural framework for its asymptotic form and for related sparse and tiling problems. Our main theorem shows that every \(r\)-colouring of a sufficiently pseudo-random \(t\)-graph can be reduced, with only \(o(n)\) loss in the largest monochromatic matching, to a colouring of \(K_n^{(t)}\) whose vertex set is partitioned into at most \(r\) parts and whose edge colours depend only on intersection profiles. The proof combines hypergraph regularity, LP duality, and convex-geometric compression. As consequences, we obtain a topology-free proof of the asymptotic AFL theorem, a sparse random transference theorem, and near-exact bounds in a linear-uniformity regime of Meunier's stable Kneser conjecture. For a graph \(H\), let \(Rt_r(H;K_n)\) be the minimum, over all \(r\)-edge-colourings of \(K_n\), of the largest monochromatic \(H\)-tiling. We prove \[ Rt_r(H;K_n)=(\beta_{r,H}+o(1))n, \] where \(\beta_{r,H}\) is effectively computable from finitely many linear programs depending only on \(H\) and \(r\). An additional multipartite Ramsey extraction is the key ingredient needed to reconstruct consistent graph templates. This gives an effective asymptotic solution to the complete-host multicolour Ramsey-tiling problem, extending the classical two-colour theorem of Burr, Erd\H{o}s and Spencer. We also determine explicit constants for several natural families, including connected non-bipartite graphs, balanced Hall-type bipartite graphs, complete bipartite graphs with three, four, and five colours, and a non-Hall bipartite example.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops a topology-free structural framework for the asymptotic Alon–Frankl–Lovász theorem on monochromatic matchings in r-edge-colorings of complete t-uniform hypergraphs and for related sparse and tiling problems. The central result states that every r-coloring of a sufficiently pseudo-random t-graph reduces, with o(n) loss in the largest monochromatic matching, to an r-partite coloring of K_n^{(t)} whose colors depend only on intersection profiles; the proof uses hypergraph regularity, LP duality, and convex-geometric compression. Consequences include an asymptotic AFL theorem, a sparse random transference theorem, near-exact bounds for a linear-uniformity case of Meunier’s stable Kneser conjecture, and the asymptotic formula Rt_r(H;K_n)=(β_{r,H}+o(1))n where β_{r,H} is computable from finitely many linear programs depending only on H and r. Explicit constants are computed for several families of graphs H, extending the two-color Burr–Erdős–Spencer theorem via multipartite extraction.

Significance. If the central reduction holds, the work supplies a combinatorial alternative to topological proofs of the asymptotic AFL theorem and yields the first effective asymptotic solution to the multicolour Ramsey-tiling problem on complete hosts. The explicit computability of β_{r,H} from finitely many LPs (depending only on H and r) and the provision of concrete constants for natural families are notable strengths; the sparse transference and multipartite extraction steps also appear to be new.

minor comments (3)
  1. §1, paragraph after the statement of the main theorem: the precise quantitative notion of 'sufficiently pseudo-random' (e.g., the required uniformity or discrepancy parameters) is invoked but not restated; a one-sentence reminder would help readers who skip to the consequences.
  2. Definition of Rt_r(H;K_n) in the abstract and §1: the minimum is taken over colorings of K_n, yet the subsequent formula is stated for the complete host; a brief parenthetical clarifying that the host is complete would avoid momentary ambiguity.
  3. The linear programs defining β_{r,H} are described as 'finitely many' and depending only on H and r; an explicit bound on the number of programs or on the dimension of the LPs (in terms of |V(H)| and r) would strengthen the computability claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the detailed summary, positive significance assessment, and recommendation of minor revision. No major comments were listed in the report, so we have no specific points to address point-by-point. We are pleased that the central reduction framework, topology-free asymptotic AFL theorem, and computable asymptotic densities for Ramsey tilings are viewed as strengths.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds from the hypergraph regularity lemma plus LP duality and convex compression to obtain an o(n)-loss reduction of any sufficiently pseudo-random t-graph colouring to an r-partite intersection-profile colouring of K_n^{(t)}; the quantity β_{r,H} is then defined directly as the optimum of finitely many linear programs on this structured class (depending only on H and r), and the asymptotic equality Rt_r(H;K_n)=(β_{r,H}+o(1))n follows by standard transference without any parameter fitting, self-definition, or load-bearing self-citation that collapses the claim to its inputs. The pseudo-randomness hypothesis is stated explicitly as a necessary precondition in the main theorem, rendering the argument self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The framework rests on the hypergraph regularity lemma (standard_math) and LP duality (standard_math); no free parameters are introduced, and no new entities are postulated. The pseudo-randomness hypothesis is a domain_assumption required for the reduction to hold with o(n) loss.

axioms (2)
  • domain assumption Hypergraph regularity lemma applies to sufficiently pseudo-random t-graphs
    Invoked to obtain the structural reduction with o(n) loss
  • standard math LP duality and convex-geometric compression control the error term
    Used to convert regularity output into the partitioned coloring

pith-pipeline@v0.9.1-grok · 5916 in / 1522 out tokens · 23424 ms · 2026-06-25T22:36:48.983995+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 3 linked inside Pith

  1. [1]

    N. Alon, L. Drewnowski, and T. Łuczak. Stable Kneser hypergraphs and ideals inNwith the Nikodým property. Proceedings of the American Mathematical Society, 137(2):467–471, 2009

    2009

  2. [2]

    N. Alon, P. Frankl, and L. Lovász. The chromatic number of kneser hypergraphs.Trans. Amer. Math. Soc., 298(1):359–370, 1986

    1986

  3. [3]

    Aragão, X

    L. Aragão, X. Cheng, R. Filipe, R. Miyazaki, D. Peng, and Z. Yan. Ramsey properties for tilings in random graphs.arXiv:2605.21471, 2026

    Pith/arXiv arXiv 2026

  4. [4]

    Balogh, A

    J. Balogh, A. Freschi, and A. Treglown. Ramsey-type problems for tilings in dense graphs.Eur. J. Comb, 131:104228, 2026

    2026

  5. [5]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs.J. Amer. Math. Soc., 28(3):669–709, 2015

    2015

  6. [6]

    Bucić and B

    M. Bucić and B. Sudakov. Tight Ramsey bounds for multiple copies of a graph.Adv. Comb., pages Paper No. 1, 22, 2023

    2023

  7. [7]

    S. A. Burr. On the Ramsey numbersr(G, nH)andr(nG, nH)whennis large.Discrete Math., 65(3):215–229, 1987

    1987

  8. [8]

    S. A. Burr, P. Erdős, and J. H. Spencer. Ramsey theorems for multiple copies of graphs.Trans. Amer. Math. Soc., 209:87–99, 1975

    1975

  9. [9]

    P.-A. Chen. On the multichromatic number ofs-stable Kneser graphs.J. Graph Theory, 79(3):233–248, 2015

    2015

  10. [10]

    Cockayne and P

    E. Cockayne and P. Lorimer. The ramsey number for stripes.J. Aust. Math. Soc., 19:252–256, 1975

    1975

  11. [11]

    Conlon and W

    D. Conlon and W. T. Gowers. Combinatorial theorems in sparse random sets.Ann. of Math. (2), 184(2):367–454, 2016

    2016

  12. [12]

    Conlon, W

    D. Conlon, W. T. Gowers, W. Samotij, and M. Schacht. On the KLR conjecture in random graphs.Israel J. Math., 203(1):535–580, 2014

    2014

  13. [13]

    Daneshpajouh

    H. Daneshpajouh. On the chromatic number of stable Kneser hypergraphs: Verifying the conjecture for new families.arXiv preprint arXiv:2509.22026, 2025

    arXiv 2025

  14. [14]

    P. Erdös. Problems and results in combinatorial analysis and combinatorial number theory. InGraph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., pages 397–406. Wiley, New York, 1991

    1988

  15. [15]

    Freschi, R

    A. Freschi, R. Martin, and A. Treglown. A random version of the burr-erdős-spencer theorem.arXiv:2605.22395, 2026

    Pith/arXiv arXiv 2026

  16. [16]

    F. Frick. Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems.Int. Math. Res. Not. IMRN, (13):4037–4061, 2020

    2020

  17. [17]

    Gishboliner, S

    L. Gishboliner, S. Glock, P. Michaeli, and A. Sgueglia. Defect and transference versions of the Alon-Frankl-Lovasz theorem.Combin. Probab. Comput., pages 1–12, 2026

    2026

  18. [18]

    Gishboliner, M

    L. Gishboliner, M. Krivelevich, and P. Michaeli. Color-biased hamilton cycles in random graphs.Random Struc- tures Algorithms, 60(3):289–307, 2022

    2022

  19. [19]

    I. Haviv. The chromatic number of kneser hypergraphs via consensus division. InProceedings of the 15th Inno- vations in Theoretical Computer Science Conference (ITCS), LIPIcs, 2024

    2024

  20. [20]

    A. Jafari. On the chromatic number of almost stable general Kneser hypergraphs.J. Comb., 13(3):437–444, 2022

    2022

  21. [21]

    J. Jonsson. On the chromatic number of generalized stable Kneser graphs.Unpublished preprint, available at https://people.kth.se/ jakobj/research. html, 2012

    2012

  22. [22]

    Keevash and P

    P. Keevash and P. Michaeli. A very robust Ramsey theorem for matchings.arXiv:2603.03139, 2026

    arXiv 2026

  23. [23]

    M. Kneser. Aufgabe 360.Jahresbericht der Deutschen Mathematiker-Vereinigung, 58:27, 1955

    1955

  24. [24]

    I. Kříž. Equivariant cohomology and lower bounds for chromatic numbers.Trans. Amer. Math. Soc., 333(2):567– 577, 1992. 35

    1992

  25. [25]

    Loo.Multicolor Ramsey numbers for disjoint unions of graphs

    S. Loo.Multicolor Ramsey numbers for disjoint unions of graphs. Ph.d. thesis, City University of New York, 1990

    1990

  26. [26]

    L. Lovász. Kneser’s conjecture, chromatic number, and homotopy.J. Combin. Theory Ser. A, 25(3):319–324, 1978

    1978

  27. [27]

    Matoušek

    J. Matoušek. A combinatorial proof of Kneser’s conjecture.Combinatorica, 24(1):163–170, 2004

    2004

  28. [28]

    F. Meunier. The chromatic number of almost stable Kneser hypergraphs.J. Combin. Theory Ser. A, 118(6):1820– 1828, 2011

    2011

  29. [29]

    Niu and L

    M. Niu and L. Wang. An exact robust Ramsey theorem for matchings.arXiv:2606.19851, 2026

    Pith/arXiv arXiv 2026

  30. [30]

    Rödl and A

    V. Rödl and A. Ruciński. Threshold functions for Ramsey properties.J. Amer. Math. Soc., 8(4):917–942, 1995

    1995

  31. [31]

    Saxton and A

    D. Saxton and A. Thomason. Hypergraph containers.Invent. Math., 201(3):925–992, 2015

    2015

  32. [32]

    M. Schacht. Extremal results for random discrete structures.Ann. of Math. (2), 184(2):333–365, 2016

    2016

  33. [33]

    Schrijver

    A. Schrijver. Vertex-critical subgraphs of Kneser graphs.Nieuw Arch. Wisk. (3), 26(3):454–461, 1978

    1978

  34. [34]

    G. M. Ziegler.Lectures on Polytopes. Springer, 1995

    1995

  35. [35]

    G. M. Ziegler. Generalized Kneser coloring theorems with combinatorial proofs.Invent. Math., 147:671–691, 2002. AppendixA.Complete bipartite tilings in five colours We prove Theorem 6.12. We repeatedly use Lemma 6.7, as well as the fact that tilings supported on disjoint same-coloured pairs may be combined. A.1.Extremal templates.The four upper-bound temp...

    2002

  36. [36]

    (0, 1 3 ,0),( 1 3 ,0, 1 3),( 1 7 , 1 7 , 1 7) R,B (0, 1 7 , 1 3),( 1 3 , 1 7 ,0),( 1 7 , 1 7 , 1

  37. [37]

    (0, 4 7 , 1 7),(0, 1 3 , 2 9),( 1 3 ,0, 1 2),( 1 7 , 1 7 , 1 7) B,R (0,0, 1 2),( 1 7 ,0, 1

  38. [38]

    (0, 1 2 ,0),( 1 7 , 1 7 , 1 7) B,B (0,0, 1 3),( 1 3 ,0,0),( 1 7 ,0, 1

  39. [39]

    Here the coordinates are ordered asA, U, W

    (0, 4 7 , 1 7),(0, 1 2 , 1 6),( 1 7 , 1 7 , 1 7). Here the coordinates are ordered asA, U, W. Taking the scalar product with(x, u, v), and applying strong duality, gives the table.□ Lemma B.3.Every3-strip3-colouringψofK n satisfiesν D(ψ)⩾ 7 78 n−O(1). Proof.Putα:= 7 78 .Since the number of strip parts and copy types is fixed, it is enough to prove that th...