WorksMathematics
A very robust Ramsey theorem for hypergraph matchings
Abstract
A fundamental result in Ramsey theory due to Alon, Frankl and Lovász gives an exact formula for the -colour Ramsey numbers of matchings in -uniform hypergraphs: if then in any -edge-colouring of there is some colour with a matching of size . We show that a very weak quasirandomness assumption suffices for this Ramsey property: we can replace by any -graph on at least vertices that is a sublinear connector, meaning that it has no balanced -partite holes of linear size. This generalises the result for (ordinary graphs) that we proved previously using a compression algorithm based on Gallai-Edmonds decompositions. This structure theory is unavailable in the hypergraph setting, so we combine two other proof methods, namely (a) simultaneous optimisation in all colours by clustering vertices using fractional cover weights from LP duality, and (b) local-to-global structure via random sampling and Kahn's matching theorem.
Introduction
Ramsey theory studies the monochromatic configurations that must occur in colourings of sufficiently large structures. In particular, Ramsey’s theorem [29] guarantees that every edge-colouring of a sufficiently large complete uniform hypergraph with a given number of colours contains a monochromatic copy of any prescribed finite hypergraph of the same uniformity. Determining the minimum number of vertices needed is a central problem in Ramsey theory. We will be concerned with the multicolour Ramsey numbers of matchings, which are known exactly, even when different matching sizes are prescribed in different colours.
We use the following notation. Given -uniform hypergraphs (-graphs for short) , we write if every -edge-colouring of has a -coloured copy of for some . Write for the set of non-negative integers and . For , put . We write , where is a matching of size . Write for . Generalising the classical theorem of Cockayne and Lorimer [9] on the multicolour Ramsey number of matchings, Alon, Frankl and Lovász [2] proved the following sharp result using topological methods.
Theorem 1.1 (Alon–Frankl–Lovász). Fix integers and . For every and every integer , we have .
Main results and applications
Over the past few decades, considerable efforts have been dedicated to establishing sparse random analogues of classical extremal and Ramsey theorems. Such transference results show that sparse random graphs or hypergraphs inherit the relevant extremal or Ramsey properties of their complete counterparts. Examples include sparse random versions of Ramsey’s theorem due to Rödl and Ruciński [30], and of Turán’s theorem due to Conlon and Gowers [10] and Schacht [31]. Gishboliner, Glock, Michaeli and Sgueglia [16] obtained such a transference version of the Alon–Frankl–Lovász theorem for sparse binomial random hypergraphs, when the target matching sizes are all equal. Here we seek to isolate the combinatorial properties underlying this transference. We prove the same asymptotic conclusion for much more general hosts satisfying a weak deterministic condition, with the random result following as a corollary.
Following [24], we say that an -graph is an -connector if, whenever are pairwise disjoint and for every , there exists an edge such that for every . Equivalently, has -partite hole number at most (see [11, 6]).
Write for the Ramsey number determined by Theorem 1.1. Our main result shows that, when , the complete -graph in Theorem 1.1 may be replaced by any -vertex -connector at the cost of additional vertices.
Theorem 1.2. For all integers and and every , there exists such that the following holds. For every and all integers satisfying and , every -vertex -connector -graph satisfies .
Theorem 1.2 resolves a conjecture posed by the authors in [24]. Our earlier proof in the graph case () relies on compression operations based on the Gallai–Edmonds decomposition. No analogue of this decomposition is known for general uniform hypergraphs, so we use a different approach (see § 1.3).
As immediate applications, Theorem 1.2 recovers both the defect and transference versions of the Alon–Frankl–Lovász theorem in [16]. Indeed, an -vertex -graph with at least edges is an -connector, where as . In addition, it is not hard to see that a binomial random -graph with edge probability , whp1, an -connector, where as . More generally, the following theorem extends Theorem 1.2 to random sparsifications of -connectors.
Theorem 1.3. For all integers and and every , there exists such that the following holds. For every and all integers satisfying , let be an -vertex -connector -graph, and let be obtained from by retaining each edge independently with probability satisfying . With probability at least , we have simultaneously for all such .
Theorem 1.2 also applies to uniformly random regular hypergraphs. Fix an integer , and let be chosen uniformly from all simple -regular -graphs on , where , and . The enumeration and coupling results in [12, 13, 20] imply that is, whp, an -connector with . In particular, for every fixed , whp every -colouring of contains a monochromatic matching of the asymptotically optimal size .
A Steiner triple system is a -graph in which every pair of vertices lies in exactly one edge. DeBiasio and Tait [11 Problem 7.4(i)] asked how large a monochromatic matching can be guaranteed in a -colouring of a Steiner triple system; we give an asymptotically sharp answer for , a uniformly random Steiner triple system on vertices is, whp, an -connector with [11, 15]. Consequently, by Theorem 1.2, for every fixed , whp every -colouring contains a monochromatic matching of the asymptotically optimal size .
Perfect-matching discrepancy
The general question in discrepancy theory is whether a ground set can be -coloured so that every set in a given family contains roughly the same number of elements of each colour. Here we seek conditions under which every -edge-colouring of an -graph contains a perfect matching with high discrepancy, meaning that significantly more than a -proportion of its edges have the same colour. Fix and , and assume that . By Theorem 1.1, every -colouring of has a perfect matching with approximately edges of one colour. The bound cannot be improved asymptotically for any -vertex -graph, as shown by the extremal construction for the complete -graph.
Write for the binomial random -graph on , in which every -set is an edge independently with probability . Johansson, Kahn and Vu [22] showed that, for some constant , contains a perfect matching whp whenever . Gishboliner, Glock and Sgueglia [17] asked whether, already at this density, whp every 2-colouring of a random -graph contains a perfect matching with approximately edges of one colour, as in the complete case. To our knowledge, this question remains open. Hàn, Lang, Marciano, Pavez-Signé, Sanhueza-Matamala, Treglown and Zárate-Guerén [21] proved that, for , whp every -colouring of contains a perfect matching with at least edges of one colour, for some . They also asked for the correct probability threshold for guaranteeing some positive linear excess over in every -colouring. The following proposition gives the asymptotically optimal colour count at , a factor above the perfect-matching existence bound. Its proof combines a simple sprinkling argument with a large monochromatic matching supplied by Theorem 1.2.
Proposition 1.4. For all integers and and every , there exists such that the following holds whenever and . Whp, every -colouring of contains a perfect matching with at least edges of one colour.
Gishboliner, Glock, Michaeli and Sgueglia [16] obtain the same colour count already for when a -colouring of all -subsets of is fixed before the random hypergraph is sampled. Their high-probability conclusion holds for each fixed colouring separately. In Proposition 1.4, an adversary may first observe the sampled hypergraph and only then colour its edges. We require, however, the larger density . We give the short proof in § 4.
Related work and motivation for the proof
There is a substantial literature on transferring Ramsey results for forests and related hypergraph structures to sparse binomial random graphs and hypergraphs. Such results have been obtained for paths [25, 14], trees [5, 14], components and loose paths in hypergraphs [7], matchings and linear forests [18], and arbitrary forests [19]. More recent results concern hypergraph matchings [16] and forest tilings [4, 27]. Liu, Turevskij, Wang and Yan [27] also give a topology-free proof of the Alon–Frankl–Lovász theorem for sufficiently large in terms of the uniformity and the number of colours , extend it to -graphs with sufficiently high minimum degree, and give another proof of the random-transference theorem in [16].
Most of these proofs follow a common approach.2 One starts with a pseudorandom host in which the edge density between any sufficiently large disjoint vertex sets is close to a common value , as holds whp for the binomial random model at the relevant densities. The multicolour weak sparse hypergraph regularity lemma (see, e.g., in [16]) partitions the vertices into clusters of almost equal size so that almost every -tuple of clusters is regular in every colour. The lower-density bound on the host ensures that some colour has density at least between the clusters of each such tuple. These tuples form an almost-complete reduced -graph on the clusters, with each edge assigned at least one such colour.
A defect version of a suitable dense Ramsey theorem then gives a monochromatic structure of asymptotically optimal size in the reduced graph. The structure sought there need not be the final object. This dense step can require a substantial argument adapted to the structure in question. Such defect versions have been obtained, for example, for matchings in graphs [18], connected matchings [26] and matchings in hypergraphs [16, 27]. Finally, regularity and density allow one to lift the reduced structure to the original host. For example, a monochromatic connected matching in the reduced graph can be lifted to a long path of the same colour in the original graph [14]. For matchings, regularity and density allow us to lift each reduced edge greedily to a matching of the same colour covering almost all vertices of its clusters. Disjoint reduced edges give disjoint lifted matchings, whose union has asymptotically optimal size.
Our aim is to weaken these pseudorandomness assumptions substantially, retaining only a simple combinatorial condition sufficient for transference. In an -vertex -graph, we ask only for a single edge crossing any pairwise disjoint vertex sets of size at least , where (that is, ). We refer to such hypergraphs as sublinear connectors; equivalently, these are -graphs with no balanced -partite holes of linear size. For Ramsey problems concerning forests, replacing pseudorandomness by this assumption is not new. In graphs, Gishboliner, Krivelevich and Michaeli [19] showed that sublinear connectors guarantee asymptotically as many edges in a monochromatic forest as complete graphs do. For two and three colours, Bal and DeBiasio [6] proved the analogous result for the order of a largest monochromatic component, and hence for a largest monochromatic tree.
One might try to imitate the regularity construction in an -connector. For simplicity, consider the diagonal case , with fixed and . Given a -colouring of an -vertex -connector -graph , our aim is a monochromatic matching of size . Partition almost all vertices into -vertex clusters. Since is an -connector, every -tuple of clusters has a crossing edge. For each -tuple, we choose one such edge of and give its colour to the corresponding edge of the complete “reduced” hypergraph on the clusters. By AFL, the reduced hypergraph has a monochromatic matching of about edges. For each edge of this reduced matching, we take the crossing edge of that we used to colour it. These crossing edges form a monochromatic matching in of the same size, a factor short of our target.
We might instead partition almost all vertices into clusters of size , where . Greedily choosing crossing edges between any of these clusters gives about disjoint edges, but these need not have the same colour. The complete reduced hypergraph now has about vertices, so an almost-perfect matching has about edges. The crossing matchings for these disjoint -tuples together give about edges. The pigeonhole principle then guarantees only about edges of one colour, short of our target when .
We return to -vertex clusters, but now choose the partition more carefully, taking account of the colouring. A small vertex cover in one colour would prevent a large matching in that colour. Our next aim is to rule out such an obstruction in at least one colour. We choose a minimum vertex cover in each colour and group the vertices according to their membership in these covers. Dividing each of the resulting sets into -vertex clusters leaves only vertices unused. Each cluster is now either contained in or disjoint from each cover. We form the reduced colouring as above. A reduced edge of colour comes from an original edge that meets the colour- cover, so one of its clusters lies entirely inside that cover. Thus a colour- reduced matching of size gives disjoint clusters inside the cover, proving that its size is at least . By AFL, some colour has minimum vertex-cover size at least . A minimum vertex cover can be much larger than a maximum matching, so this does not yet give the desired matching.
For fractional matchings, however, LP duality states that the maximum fractional matching weight equals the minimum fractional vertex-cover weight. We therefore adapt the partition argument to minimum fractional vertex covers, using closeness of weights in place of membership in a set. We associate each vertex with the vector of its cover weights in . Small boxes in this cube replace the membership classes above: within each box, we divide the vertices into -vertex clusters. Since , we can let the box diameters tend to zero slowly enough that the number of unused vertices remains sublinear. All colours must be controlled simultaneously, since the colour supplied by AFL is not known in advance. For a crossing edge of colour , the cover weights of its vertices satisfy . Near constancy within the clusters then gives total colour- cover weight at least on these clusters, up to the clustering error. The total error is therefore sublinear. As before, summing over the disjoint clusters of a reduced monochromatic matching gives total cover weight at least . LP duality then gives a monochromatic fractional matching of weight .
To pass to an ordinary matching, we use Kahn’s theorem [23]. It gives a matching of almost the same size if the total fractional weight on edges containing any pair of distinct vertices is . Our fractional construction need not have this property. For a uniformly random -vertex set , a given vertex belongs to with probability , whereas a given pair belongs to with probability . This suggests averaging fractional matchings on small induced subgraphs. Each is still an -connector, so, provided , the fractional result gives a monochromatic fractional matching of weight at least in every . We average these matchings over all -sets. The average has total weight at least and total weight at most through any vertex. Scaling the average by therefore restores the desired total weight while keeping every vertex sum at most . Each local fractional matching puts weight at most through any pair, and a given pair lies in with probability at most . After scaling, the total weight through any pair is therefore at most . Taking makes these pair weights , as required by Kahn’s theorem.
The fractional matchings in different may have different colours. Their average may therefore assign positive weight to edges of several colours. To choose a common colour without losing a constant factor, we use concentration. By the pigeonhole principle, some colour attains the local bound above on at least a proportion of the -sets. The maximum fractional matching weight in that colour changes by at most when one vertex of the set is replaced. Azuma’s inequality therefore implies concentration within of its mean. Since the large value occurs on a positive proportion of the sets, the mean must also be at least . We now average maximum fractional matchings in this fixed colour and scale by as above. The resulting fractional matching has total weight at least and small pair weights, so Kahn’s theorem gives an ordinary monochromatic matching of the required size.
Preliminaries
A -multi-colouring of an -graph is a sequence where is an -graph for every , and . We call the underlying -graph of the coloured -graph . An edge is said to have colour if . Note that we allow an edge to possess multiple colours and that, for the Ramsey properties considered here, it is equivalent to consider multi-colourings or usual colourings, where each edge has exactly one colour. We will therefore abuse terminology and also refer to -multi-colourings as -colourings.
The matching number of a hypergraph is the size of a maximum matching in . A fractional matching in a hypergraph is a function such that for every . Its weight is . The fractional matching number is the maximum weight of a fractional matching in .
We will use the following well-known consequence of LP duality to find large fractional matchings. A fractional vertex cover of a hypergraph is a function such that for every . The weight of is the sum of over all . The minimum weight of a fractional vertex cover of is denoted by .
Lemma 2.1 (Fractional matching–cover duality, see, e.g., [8]). For every hypergraph , we have
We will use the following concentration inequality when passing from fractional to ordinary matchings, to show that fractional matching numbers in random induced subhypergraphs are typically close to their means. The two-sided form below follows by applying Azuma’s inequality (see, e.g., [3 Theorem 7.2.1]) to a martingale and its negative.
Lemma 2.2 (Two-sided Azuma inequality). Let be a martingale satisfying for every integer . For every we have
The starting point of our strategy is the following simple clustering lemma, applied to the vector obtained from fractional cover weights in each colour, which will partition the vertices into clusters on most of which the weights are approximately constant. We write for diameter in the metric.
Lemma 2.3 (Clustering). For every integer and every , there exists such that the following holds. Let be an -element set and let be an integer satisfying . Let . Put . There exists an equipartition , with cluster sizes differing by at most , such that
Proof. Partition into cubes of side length at most . In each coordinate, use intervals closed on the left and open on the right, including in the last interval. Choose an ordering of in which every element of precedes every element of whenever . Split this order into consecutive clusters whose sizes differ by at most . At most clusters have images meeting more than one cube. ysady
If a cluster’s image lies in one cube, its diameter is at most ; otherwise it is at most 1. Since implies , choosing sufficiently small ensures that . Therefore
as required.
Fractional matchings
In this section we prove the following fractional version of Theorem 1.2.
Theorem 3.1. For all integers and and every , there exists such that the following holds. Let , let be an -vertex -connector -graph, let be a -colouring of , and let . If and , then there exists such that .
The proof uses the following lemma that clusters vertices according to the fractional cover weights in each colour.
Lemma 3.2. For all integers and and every , there exists such that the following holds. Let be -graphs on a common -element vertex set , and let be an integer satisfying . Put . Then there exists an equipartition with the following property. For every , let be the -graph on whose edges are the sets for which has an edge meeting every , , once. Then, for every ,
Proof. Choose as in Lemma 2.3 for and . For every , choose an optimal fractional vertex cover of . We may assume that for every . Apply Lemma 2.3 to to obtain an equipartition such that
For and , put . For every , we have . Since does not depend on ,
Summing over , using and by Lemma 2.1, gives
Fix . For every edge of , choose an edge of meeting every , , once. Since is a fractional vertex cover of ,
Thus the weights form a fractional vertex cover of . By Lemma 2.1 and (1),
Rearranging gives , as required.
We now deduce Theorem 3.1. We use the following properties that are immediate from the definition of . Fix integers and . Write . For and every integer , we have
If and satisfy for every , then
Proof of Theorem 3.1. Put and . For these , and , let be supplied by Lemma 3.2. Put . Put and . Since , and , we have
Moreover, and give , so . Using and (2), we obtain
where the last inequality follows from . Apply Lemma 3.2 to . The resulting graphs form a -colouring of , since is an -connector. Put for every and . Since , every is positive. Applying (3) with and in place of gives
By Theorem 1.1, some has a matching of size . For this , Lemma 3.2 and give
Integral matchings
Now we present the second main ingredient of our proof strategy. The two key points of the following theorem are (a) passing from fractional to integral matchings, and (b) passing from potentially several local choices of to a single global choice of .
Theorem 4.1 (Local-to-global, fractional-to-integral). For all integers and and every , there exist and such that the following holds. Let and be positive integers satisfying , let be -graphs on a common -element vertex set , and let . Suppose that, for every , there exists such that . Then there exists such that
We will address point (a) via the following matching theorem due to Kahn. For a fractional matching in a hypergraph , put
Theorem 4.2 ([23 Theorem 1.2(a)]). For every integer and every , there exists such that, if is a hypergraph whose edges have size at most and is a fractional matching in with , then
We will address point (b) via the following application of Azuma’s inequality, which provides a single colour with a fractional matching suitable for applying Theorem 4.2.
Lemma 4.3. For all integers and and every , there exists such that the following holds. Let , let be -graphs on a common -element vertex set , and let . Suppose that, for every , there exists such that . Then there exist and a fractional matching in such that and
The averaging argument in the proof below is similar to that of Alon, Frankl, Huang, Rödl, Ruciński and Sudakov [1].
Proof. Choose sufficiently large that, for every , . Let be chosen uniformly from . For and , put and . We will show that is concentrated about its mean . To this end, we apply Azuma’s inequality. Fix and order the vertices of uniformly at random as . For , put
Then is a martingale with and .
We need to check that for . Fix and put . For , write . We first show that for any . Pair each possible final set when with itself if , and with otherwise. This pairs the possible final sets for the two choices one-to-one; under either choice these sets are uniform. Exchanging one vertex of changes by at most 1, since deleting from a fractional matching all edges through the removed vertex loses weight at most 1. Thus . Before is exposed, each vertex of is equally likely to be chosen, so
Applying Lemma 2.2 gives
By the union bound over all and the choice of ,
Hence there exists an -set such that for every . By the hypothesis of the lemma, there exists such that . Thus .
For every -set , choose an optimal fractional matching in , and put for every edge of not contained in . For every , put
For every ,
so is a fractional matching in . Moreover,
Finally,
We conclude this section with the proof of its main result.
Proof of Theorem 4.1. It suffices to consider . Apply Theorem 4.2 with in place of , and let be the resulting constant. Apply Lemma 4.3 with in place of , and let be the resulting constant.
By Lemma 4.3, there exist and a fractional matching in such that
and . By Theorem 4.2 and , we have
Proofs of the main theorems
We now assemble the ingredients from the previous sections to prove the main theorems stated in the introduction.
Proof of Theorem 1.2. It suffices to consider . Put and . For these , and , let and be supplied by Theorem 4.1, and let be supplied by Lemma 3.2. Put
Let and satisfy the assumptions of Theorem 1.2, and fix a -colouring of . Put and . Since , we have . By our choice of , we have , so . Our choice of also gives . Moreover, , and hence . Finally, .
Put , so . Put and . By (2) and the hypothesis , we have .
For every , the definition of gives
since and every summand is nonnegative. Thus for every . Put for every and . Since , every is positive. Applying (3) with and in place of gives
For every , apply Lemma 3.2 to . The resulting graphs form a -colouring of , since is an -connector. By Theorem 1.1, there exists such that has a matching of size . Since , we have .
Since , and , Lemma 3.2 gives
Thus Theorem 4.1, with in place of , gives some such that
To prove Theorem 1.3, we use the following lemma to verify the connector hypothesis of Theorem 1.2 for the sparsified hypergraph.
Lemma 5.1. For every integer and every , there exists such that the following holds. Let and be positive integers satisfying , let be an -vertex -connector -graph, and let be obtained from by retaining each edge independently with probability . With probability at least , is a -connector.
Proof. Put and choose such that . Put . Fix pairwise disjoint -sets . We want to contain an edge meeting each once. To this end, we first find many such edges in . Partition each of into disjoint -sets, ignoring the remaining vertices. For each , choose one of these -sets inside and call it . For each , look for an edge consisting of and one vertex from each . Such an edge can be absent for at most vertices: of them together with would contradict the connector property. Choosing one edge for each of the other vertices gives at least distinct edges. Each chosen edge has exactly one vertex in each . For each , its vertex in lies in exactly one of the disjoint -sets, so this vertex determines . Hence no edge is counted for two different choices of . Since , we have and . The number of edges of meeting every once is therefore at least
Using , the probability that none of these edges survives is at most
There are at most choices of the disjoint sets , since each vertex lies in one of these sets or outside their union. By the union bound, the probability that is not an -connector is at most
where the last inequality uses .
Proof of Theorem 1.3. Let be the constant supplied by Theorem 1.2 for , and . Put , and let be supplied by Lemma 5.1 for and . We may assume that . Since , we have . In particular, and, since , . Thus . Lemma 5.1 implies that, with probability at least , is a -connector. On this event, Theorem 1.2 gives simultaneously for all satisfying .
We prove Proposition 1.4 by using Theorem 1.2 to find a large monochromatic matching and then matching the remaining vertices. The remaining vertex set depends on the colouring, so we will show that, whp, every sufficiently large vertex set of size divisible by has a perfect matching. We use the following perfect-matching theorem of Johansson, Kahn and Vu [22].
Theorem 5.2 ([22]). For every integer , there exists such that, whenever and , the random -graph contains a perfect matching whp.
We prove the following lemma by a simple sprinkling argument, also used in [21].
Lemma 5.3. For every integer and every , there exists such that, if and , then whp contains a perfect matching for every satisfying and .
Proof. Let be the constant supplied by Theorem 5.2, and take . Choose an integer with , and put and , and let be independent copies of on the same vertex set. Fix with and . Since , our choice of gives for all sufficiently large . By Theorem 5.2, each has a perfect matching with probability at least . Hence the probability that none of has a perfect matching is at most . Put . By the union bound over the at most choices of with and , the probability that has no perfect matching for some such is at most . The union has the distribution of , where . Coupling with completes the proof.
Proof of Proposition 1.4. Put and . Choose as in Theorem 1.2 for , and put . The definition of gives
Since , for all sufficiently large we have and
Thus . Put , let be supplied by Lemma 5.3 for and , and let with . There are at most ordered choices of pairwise disjoint sets . If each set has size at least , the probability that no edge meets them all is at most . Since , a union bound shows that is an -connector whp. By Lemma 5.3, whp also has a perfect matching for every with and .
Fix a graph with both properties and an arbitrary -colouring of . By Theorem 1.2, there exists a monochromatic matching of size ; if necessary, discard edges so that its size is exactly . Put . Then and, for all sufficiently large ,
Hence has a perfect matching . The union is a perfect matching and contains at least edges of one colour.
The extra factor over the perfect-matching threshold comes from the independent copies of on the same vertex set in the proof of Lemma 5.3: they make the failure probability small enough to take a union bound over every uncovered vertex set.
Concluding remarks
Recall that our earlier graph result [24] guarantees for every -vertex -connector graph whenever . For , let be the least such that every -colouring of every -vertex -connector -graph contains a colour- matching of size for some . In this notation, the result of Niu and Wang [28] states that
This suggests the following analogue for -uniform hypergraphs:
However, this formula is false already for . To see this, let be the Fano plane, the Steiner triple system on seven vertices.
Proposition 6.1. The Fano plane is a -connector -graph and satisfies .
Proof. Any two Fano lines meet, so . To see the connector property, let be three pairwise disjoint pairs of Fano points, and let be the remaining point. There are four Fano lines avoiding . If none of them has one point in each of , then each contains both points of one of these pairs. Two different lines cannot contain the same pair, since two Fano points determine a unique line. The three pairs therefore cannot account for all four lines, a contradiction.
For , and , the right-hand side of (4) is . Colouring every edge of red gives a -free colouring of a -connector -graph on seven vertices, so .
The right-hand side of (4) is nevertheless a lower bound for , as shown by the following two constructions.
Consider disjoint sets of size and of size for . Every -set that meets is an edge, coloured by some for which it meets .
Label the colours so that . Take the complete -graph on the disjoint union of sets with and for . Add isolated vertices. Colour an edge with some if it meets , and otherwise with colour 1.
Although (4) fails, it seems plausible that the additive error above should remain linear in , as in the case. The following conjecture proposes such an interpolation between and Theorem 1.2 for the full range of .
Conjecture 6.2. For all integers and , there exists such that, for every integer and every
Statement on AI use
OpenAI’s Codex was used for editorial assistance, proofreading and literature searches. The mathematical proof details and exposition are entirely due to the authors.
References
- [1]Noga Alon, Peter Frankl, Hao Huang, Vojtěch Rödl, Andrzej Ruciński and Benny Sudakov, Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, Journal of Combinatorial Theory. Series A 119 (2012), no. 6, 1200–1215. MR2915641 ↑9arxiv.org/abs/1107.1219
- [2]Noga Alon, Péter Frankl and László Lovász, The chromatic number of Kneser hypergraphs, Transactions of the American Mathematical Society 298 (1986), no. 1, 359–370. MR857448 ↑1DOI
- [3]Noga Alon and Joel H. Spencer, The probabilistic method, Fourth, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR3524748 ↑6
- [4]Lucas Aragão, Xinbu Cheng, Rafael Filipe, Rafael Miyazaki, Danni Peng and Zhifei Yan, Ramsey properties for tilings in random graphs, arXiv e-prints (May 2026), available at arXiv:2605.21471. ↑3, 4arxiv.org/abs/2605.21471
- [5]Deepak Bal and Louis DeBiasio, Partitioning random graphs into monochromatic components, Electronic Journal of Combinatorics 24 (2017), no. 1, Paper P1.18, 25 pp. ↑3arxiv.org/abs/1509.09168
- [6]Deepak Bal and Louis DeBiasio, Large monochromatic components in expansive hypergraphs, Combinatorics, Probability and Computing 33 (2024), no. 4, 467–483. ↑2, 4DOI
- [7]Patrick Bennett, Louis DeBiasio, Andrzej Dudek and Sean English, Large monochromatic components and long monochromatic cycles in random hypergraphs, European Journal of Combinatorics 76 (2019), 123–137. ↑3arxiv.org/abs/1709.02990
- [8]Claude Berge, Hypergraphs: Combinatorics of finite sets, North-Holland Mathematical Library, vol. 45, North-Holland, Amsterdam, 1989. ↑6
- [9]Ernest J. Cockayne and Peter J. Lorimer, The Ramsey number for stripes, Journal of the Australian Mathematical Society 19 (1975), no. 2, 252–256. MR371733 ↑1DOI
- [10]David Conlon and W. Timothy Gowers, Combinatorial theorems in sparse random sets, Annals of Mathematics. Second Series 184 (2016), no. 2, 367–454. ↑2arxiv.org/abs/1011.4310
- [11]Louis DeBiasio and Michael Tait, Large monochromatic components in 3-edge-colored Steiner triple systems, Journal of Combinatorial Designs 28 (2020), no. 6, 428–444. ↑2, 3arxiv.org/abs/1908.00837
- [12]Andrzej Dudek, Alan Frieze, Andrzej Ruciński and Matas Šileikis, Approximate counting of regular hypergraphs, Information Processing Letters 113 (2013), no. 19–21, 785–788. ↑2
- [13]Andrzej Dudek, Alan Frieze, Andrzej Ruciński and Matas Šileikis, Embedding the Erdős–Rényi hypergraph into the random regular hypergraph and Hamiltonicity, Journal of Combinatorial Theory. Series B 122 (2017), 719–740. ↑2
- [14]Andrzej Dudek and Paweł Prałat, On some multicolor Ramsey properties of random graphs, SIAM Journal on Discrete Mathematics 31 (2017), no. 3, 2079–2092. ↑3, 4DOI
- [15]Asaf Ferber and Matthew Kwan, Almost all Steiner triple systems are almost resolvable, Forum of Mathematics, Sigma 8 (2020), e39, 24. ↑3DOI
- [16]Lior Gishboliner, Stefan Glock, Peleg Michaeli and Amedeo Sgueglia, Defect and transference versions of the Alon–Frankl–Lovász theorem, Combinatorics, Probability and Computing 35 (2026), 542–553. ↑2, 3, 4
- [17]Lior Gishboliner, Stefan Glock and Amedeo Sgueglia, Tight Hamilton cycles with high discrepancy, Combinatorics, Probability and Computing 34 (2025), no. 4, 565–584. ↑3DOI
- [18]Lior Gishboliner, Michael Krivelevich and Peleg Michaeli, Color-biased Hamilton cycles in random graphs, Random Structures & Algorithms 60 (2022), no. 3, 289–307. ↑3, 4DOI
- [19]Lior Gishboliner, Michael Krivelevich and Peleg Michaeli, Discrepancies of spanning trees and Hamilton cycles, Journal of Combinatorial Theory. Series B 154 (2022), 262–291. ↑3, 4arxiv.org/abs/2012.05155
- [20]Catherine Greenhill, Mikhail Isaev, Tamás Makai and Brendan D. McKay, Degree sequences of sufficiently dense random uniform hypergraphs, Combinatorics, Probability and Computing 32 (2023), no. 2, 183–224. ↑2arxiv.org/abs/2106.08100
- [21]Hiệp Hàn, Richard Lang, João Pedro Marciano, Mátyás Pavez-Signé, Nicolás Sanhueza-Matamala, Andrew Treglown and Camila Zárate-Guérén, Colour-bias perfect matchings in hypergraphs, SIAM Journal on Discrete Mathematics 39 (2025), no. 3, 1894–1916. ↑3, 12arxiv.org/abs/2408.11016
- [22]Anders Johansson, Jeff Kahn and Van Vu, Factors in random graphs, Random Structures & Algorithms 33 (2008), no. 1, 1–28. ↑3, 12arxiv.org/abs/0803.3406
- [23]Jeff Kahn, A linear programming perspective on the Frankl–Rödl–Pippenger theorem, Random Structures & Algorithms 8 (1996), no. 2, 149–157. MR1607104 ↑5, 9doi.org/10.1002/(sici)1098-2418(199603)8:2<149::aid-rsa5>3.3.co;2-s
- [24]Peter Keevash and Peleg Michaeli, A very robust Ramsey theorem for matchings, arXiv e-prints (March 2026), arXiv:2603.03139, available at arXiv:2603.03139. ↑2, 13arxiv.org/abs/2603.03139
- [25]Shoham Letzter, Path Ramsey number for random graphs, Combinatorics, Probability and Computing 25 (2016), no. 4, 612–622. ↑3DOI
- [26]Shoham Letzter, An improvement on Łuczak’s connected matchings method, Bulletin of the London Mathematical Society 54 (2022), no. 2, 609–623. ↑4arxiv.org/abs/2009.03119
- [27]Hong Liu, Maksim Turevskii, Lanchao Wang and Zhifei Yan, Structural reductions for monochromatic matchings and Ramsey tilings, arXiv e-prints (June 2026), arXiv:2606.24863, available at arXiv:2606.24863. ↑3, 4arxiv.org/abs/2606.24863
- [28]Mengyuan Niu and Lanchao Wang, An exact robust Ramsey theorem for matchings, arXiv e-prints (June 2026), arXiv:2606.19851, available at arXiv:2606.19851. ↑13arxiv.org/abs/2606.19851
- [29]Frank P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society. Second Series 30 (1930), no. 1, 264–286. ↑1
- [30]Vojtěch Rödl and Andrzej Ruciński, Threshold functions for Ramsey properties, Journal of the American Mathematical Society 8 (1995), no. 4, 917–942. ↑2DOI
- [31]Mathias Schacht, Extremal results for random discrete structures, Annals of Mathematics. Second Series 184 (2016), no. 2, 333–365. ↑2