betaFeedback

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 qq-colour Ramsey numbers of matchings in rr-uniform hypergraphs: if n≥AFLr(t)=(r−1)∥t∥∞+1+∑j=1q(tj−1)n\ge\mathsf{AFL}_r(\mathbf{t})=(r-1)\|\mathbf{t}\|_\infty+1+\sum_{j=1}^q(t_j-1) then in any qq-edge-colouring of KnrK^r_n there is some colour jj with a matching of size tjt_j. We show that a very weak quasirandomness assumption suffices for this Ramsey property: we can replace KnrK^r_n by any rr-graph HH on at least AFLr(t)+o(n)\mathsf{AFL}_r(\mathbf{t})+o(n) vertices that is a sublinear connector, meaning that it has no balanced rr-partite holes of linear size. This generalises the result for r=2r=2 (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 rr-uniform hypergraphs (rr-graphs for short) F1,…,FqF_1,\ldots,F_q, we write H→(F1,…,Fq)H \to(F_1,\ldots,F_q) if every qq-edge-colouring of HH has a jj-coloured copy of FjF_j for some j∈[q]:={1,…,q}j \in[q] := \{1,\ldots,q\}. Write N\mathbb{N} for the set of non-negative integers and N+=N∖{0}\mathbb{N}_+ = \mathbb{N} \setminus\{0\}. For t=(t1,…,tq)∈N+q\mathbf{t} = (t_1,\ldots,t_q) \in\mathbb{N}_+^q, put ∥t∥∞=max⁡j∈[q]tj\|\mathbf{t}\|_\infty= \max_{j\in[q]} t_j. We write tKrr=(t1Krr,…,tqKrr)\mathbf{t}K_r^r = (t_1K_r^r,\ldots,t_qK_r^r), where tKrrtK_r^r is a matching of size tt. Write Λt=∑i=1q(ti−1)\Lambda_{\mathbf{t}} = \sum_{i=1}^q(t_i-1) for t∈N+q\mathbf{t} \in\mathbb{N}_+^q. 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 r≥2r \ge2 and q≥1q \ge1. For every t∈N+q\mathbf{t} \in\mathbb{N}_+^q and every integer n≥(r−1)∥t∥∞+Λt+1n \ge(r-1)\|\mathbf{t}\|_\infty+ \Lambda_{\mathbf{t}} + 1, we have Knr→tKrrK_n^r \to\mathbf{t}K_r^r.

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 rr-graph HH is an ss-connector if, whenever A1,…,Ar⊆V(H)A_1,\ldots,A_r \subseteq V(H) are pairwise disjoint and ∣Ai∣≥s|A_i| \ge s for every i∈[r]i \in[r], there exists an edge e∈E(H)e \in E(H) such that ∣e∩Ai∣=1|e \cap A_i| = 1 for every i∈[r]i \in[r]. Equivalently, HH has rr-partite hole number at most s−1s-1 (see [11, 6]).

Write AFL⁡r(t)=(r−1)∥t∥∞+Λt+1\operatorname{AFL}_r(t)=(r-1)\|t\|_\infty+\Lambda_t+1 for the Ramsey number determined by Theorem 1.1. Our main result shows that, when s=o(n)s=o(n), the complete rr-graph in Theorem 1.1 may be replaced by any nn-vertex ss-connector at the cost of o(n)o(n) additional vertices.

Theorem 1.2. For all integers r≥2r \ge2 and q≥1q \ge1 and every η>0\eta> 0, there exists ε>0\varepsilon> 0 such that the following holds. For every t∈N+t \in\mathbb{N}_{+} and all integers 1≤s≤n1 \le s \le n satisfying s<εns < \varepsilon n and n≥AFL⁡r(t)+ηnn \ge\operatorname{AFL}_r(t)+\eta n, every nn-vertex ss-connector rr-graph HH satisfies H→tKrH \to tK_r.

Theorem 1.2 resolves a conjecture posed by the authors in [24]. Our earlier proof in the graph case (r=2r=2) 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 nn-vertex rr-graph with at least (1−δ)(nr)(1-\delta)\binom{n}{r} edges is an εn\varepsilon n-connector, where ε=ε(δ)→0\varepsilon=\varepsilon(\delta)\to0 as δ→0\delta\to0. In addition, it is not hard to see that a binomial random rr-graph with edge probability p≥Cn1−rp \ge Cn^{1-r}, whp1, an εn\varepsilon n-connector, where ε=ε(C)→0\varepsilon=\varepsilon(C)\to0 as C→∞C\to\infty. More generally, the following theorem extends Theorem 1.2 to random sparsifications of ss-connectors.

Theorem 1.3. For all integers r≥2r \ge2 and q≥1q \ge1 and every η>0\eta> 0, there exists C>0C > 0 such that the following holds. For every t∈N+t \in\mathbb{N}_{+} and all integers 1≤s≤n1 \le s \le n satisfying n≥AFL⁡r(t)+ηnn \ge\operatorname{AFL}_r(t)+\eta n, let HH be an nn-vertex ss-connector rr-graph, and let HpH_p be obtained from HH by retaining each edge independently with probability p∈[0,1]p \in[0,1] satisfying p≥C(s/n)r−1p \ge C(s/n)^{r-1}. With probability at least 1−e−n1-e^{-n}, we have Hp→tKrH_p \to tK_r simultaneously for all such tt.

Theorem 1.2 also applies to uniformly random regular hypergraphs. Fix an integer r≥3r \ge3, and let GG be chosen uniformly from all simple dd-regular rr-graphs on [n][n], where d=d(n)→∞d=d(n)\to\infty, r∣ndr \mid nd and d≤(n−1r−1)d \le\binom{n-1}{r-1}. The enumeration and coupling results in [12, 13, 20] imply that GG is, whp, an ss-connector with s=o(n)s=o(n). In particular, for every fixed q≥1q \ge1, whp every qq-colouring of GG contains a monochromatic matching of the asymptotically optimal size (1/r+q−1)−o(1)n(1/r+q-1)-o(1)n.

A Steiner triple system is a 33-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 22-colouring of a Steiner triple system; we give an asymptotically sharp answer for n≡1,3(mod6)n \equiv1,3 \pmod{6}, a uniformly random Steiner triple system on nn vertices is, whp, an ss-connector with s=o(n)s=o(n) [11, 15]. Consequently, by Theorem 1.2, for every fixed q≥1q \ge1, whp every qq-colouring contains a monochromatic matching of the asymptotically optimal size (1/(q+2)−o(1))n(1/(q+2)-o(1))n.

Perfect-matching discrepancy

The general question in discrepancy theory is whether a ground set can be qq-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 qq-edge-colouring of an rr-graph contains a perfect matching with high discrepancy, meaning that significantly more than a 1/q1/q-proportion of its edges have the same colour. Fix r≥3r \ge3 and q≥2q \ge2, and assume that r∣nr \mid n. By Theorem 1.1, every qq-colouring of KnrK_n^r has a perfect matching with approximately n/(r+q−1)n/(r+q-1) edges of one colour. The bound cannot be improved asymptotically for any nn-vertex rr-graph, as shown by the extremal construction for the complete rr-graph.

Write G(r)(n,p)\mathbf{G}^{(r)}(n,p) for the binomial random rr-graph on [n][n], in which every rr-set is an edge independently with probability pp. Johansson, Kahn and Vu [22] showed that, for some constant A=A(r)>0A=A(r)>0, G(r)(n,p)\mathbf{G}^{(r)}(n,p) contains a perfect matching whp whenever p≥An1−rlog⁡np \ge An^{1-r}\log n. Gishboliner, Glock and Sgueglia [17] asked whether, already at this density, whp every 2-colouring of a random rr-graph contains a perfect matching with approximately n/(r+1)n/(r+1) 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 p≥Cn1−r/2p \ge Cn^{1-r/2}, whp every qq-colouring of G(r)(n,p)\mathbf{G}^{(r)}(n,p) contains a perfect matching with at least n/(rq)+γr,qnn/(rq)+\gamma_{r,q}n edges of one colour, for some γr,q>0\gamma_{r,q}>0. They also asked for the correct probability threshold for guaranteeing some positive linear excess over n/(rq)n/(rq) in every qq-colouring. The following proposition gives the asymptotically optimal colour count at p≥Cn2−rlog⁡np \ge Cn^{2-r}\log n, a factor nn 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 r≥3r \ge3 and q≥2q \ge2 and every 0<μ<10<\mu<1, there exists C>0C>0 such that the following holds whenever r∣nr \mid n and p≥Cn2−rlog⁡np \ge Cn^{2-r}\log n. Whp, every qq-colouring of G∼G(r)(n,p)G\sim\mathbf{G}^{(r)}(n,p) contains a perfect matching with at least (1−μ)n/(r+q−1)(1-\mu)n/(r+q-1) edges of one colour.

Gishboliner, Glock, Michaeli and Sgueglia [16] obtain the same colour count already for p≥Cn1−rlog⁡np \ge Cn^{1-r}\log n when a qq-colouring of all rr-subsets of [n][n] 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 p≥Cn2−rlog⁡np \ge Cn^{2-r}\log n. 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 nn sufficiently large in terms of the uniformity rr and the number of colours qq, extend it to rr-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 rr sufficiently large disjoint vertex sets is close to a common value pp, 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 rr-tuple of clusters is regular in every colour. The lower-density bound on the host ensures that some colour has density at least p/(2q)p/(2q) between the clusters of each such tuple. These tuples form an almost-complete reduced rr-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 nn-vertex rr-graph, we ask only for a single edge crossing any rr pairwise disjoint vertex sets of size at least ss, where s≪ns \ll n (that is, s/n→0s/n \to0). We refer to such hypergraphs as sublinear connectors; equivalently, these are rr-graphs with no balanced rr-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 ss-connector. For simplicity, consider the diagonal case t1=⋯=tqt_1 = \cdots= t_q, with r,qr,q fixed and s≪ns \ll n. Given a qq-colouring of an nn-vertex ss-connector rr-graph HH, our aim is a monochromatic matching of size ∼n/(r+q−1)\sim n/(r+q-1). Partition almost all vertices into ss-vertex clusters. Since HH is an ss-connector, every rr-tuple of clusters has a crossing edge. For each rr-tuple, we choose one such edge of HH 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 n/(s(r+q−1))n/(s(r+q-1)) edges. For each edge of this reduced matching, we take the crossing edge of HH that we used to colour it. These crossing edges form a monochromatic matching in HH of the same size, a factor ss short of our target.

We might instead partition almost all vertices into clusters of size ℓ\ell, where s≪ℓ≪ns \ll\ell\ll n. Greedily choosing crossing edges between any rr of these clusters gives about ℓ\ell disjoint edges, but these need not have the same colour. The complete reduced hypergraph now has about n/ℓn/\ell vertices, so an almost-perfect matching has about n/(rℓ)n/(r\ell) edges. The crossing matchings for these disjoint rr-tuples together give about n/rn/r edges. The pigeonhole principle then guarantees only about n/(rq)n/(rq) edges of one colour, short of our target when q≥2q \ge2.

We return to ss-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 qq covers. Dividing each of the resulting 2q2^q sets into ss-vertex clusters leaves only O(s)=o(n)O(s)=o(n) 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 jj comes from an original edge that meets the colour-jj cover, so one of its clusters lies entirely inside that cover. Thus a colour-jj reduced matching of size kk gives kk disjoint clusters inside the cover, proving that its size is at least ksks. By AFL, some colour has minimum vertex-cover size at least ∼n/(r+q−1)\sim n/(r+q-1). 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 qq cover weights in [0,1]q[0,1]^q. Small boxes in this cube replace the membership classes above: within each box, we divide the vertices into ss-vertex clusters. Since s≪ns\ll n, 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 jj, the cover weights a1,…,ara_1,\ldots,a_r of its vertices satisfy a1+⋯+ar≥1a_1+\cdots+a_r\ge1. Near constancy within the clusters then gives total colour-jj cover weight at least s(a1+⋯+ar)≥ss(a_1+\cdots+a_r)\ge s 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 ∼n/(r+q−1)\sim n/(r+q-1). LP duality then gives a monochromatic fractional matching of weight ∼n/(r+q−1)\sim n/(r+q-1).

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 o(1)o(1). Our fractional construction need not have this property. For a uniformly random ℓ\ell-vertex set UU, a given vertex belongs to UU with probability ℓ/n\ell/n, whereas a given pair belongs to UU with probability ∼ℓ2/n2\sim\ell^2/n^2. This suggests averaging fractional matchings on small induced subgraphs. Each H[U]H[U] is still an ss-connector, so, provided s≪ℓs\ll\ell, the fractional result gives a monochromatic fractional matching of weight at least ∼ℓ/(r+q−1)\sim\ell/(r+q-1) in every H[U]H[U]. We average these matchings over all ℓ\ell-sets. The average has total weight at least ∼ℓ/(r+q−1)\sim\ell/(r+q-1) and total weight at most ℓ/n\ell/n through any vertex. Scaling the average by n/ℓn/\ell therefore restores the desired total weight while keeping every vertex sum at most 11. Each local fractional matching puts weight at most 11 through any pair, and a given pair lies in UU with probability at most (ℓ/n)2(\ell/n)^2. After scaling, the total weight through any pair is therefore at most ℓ/n\ell/n. Taking ℓ≪n\ell\ll n makes these pair weights o(1)o(1), as required by Kahn’s theorem.

The fractional matchings in different H[U]H[U] 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 1/q1/q proportion of the ℓ\ell-sets. The maximum fractional matching weight in that colour changes by at most 11 when one vertex of the set is replaced. Azuma’s inequality therefore implies concentration within o(ℓ)o(\ell) of its mean. Since the large value occurs on a positive proportion of the sets, the mean must also be at least ∼ℓ/(r+q−1)\sim\ell/(r+q-1). We now average maximum fractional matchings in this fixed colour and scale by n/ℓn/\ell as above. The resulting fractional matching has total weight at least ∼n/(r+q−1)\sim n/(r+q-1) and small pair weights, so Kahn’s theorem gives an ordinary monochromatic matching of the required size.

Preliminaries

A qq-multi-colouring of an rr-graph H=(V,E)H=(V,E) is a sequence H=(H1,…,Hq)\mathcal{H}=(H_1,\ldots,H_q) where Hj=(V,Ej)H_j=(V,E_j) is an rr-graph for every j∈[q]j\in[q], and ⋃jEj=E\bigcup_j E_j=E. We call HH the underlying rr-graph of the coloured rr-graph H\mathcal{H}. An edge ee is said to have colour jj if e∈Eje\in E_j. 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 qq-multi-colourings as qq-colourings.

The matching number ν(F)\nu(F) of a hypergraph FF is the size of a maximum matching in FF. A fractional matching in a hypergraph FF is a function x:E(F)→[0,∞)x:E(F)\to[0,\infty) such that ∑e∋vx(e)≤1\sum_{e\ni v}x(e)\le1 for every v∈V(F)v\in V(F). Its weight is ∑e∈E(F)x(e)\sum_{e\in E(F)}x(e). The fractional matching number ν∗(F)\nu^*(F) is the maximum weight of a fractional matching in FF.

We will use the following well-known consequence of LP duality to find large fractional matchings. A fractional vertex cover of a hypergraph FF is a function w:V(F)→[0,∞)w:V(F)\to[0,\infty) such that ∑v∈ew(v)≥1\sum_{v\in e}w(v)\ge1 for every e∈E(F)e\in E(F). The weight of ww is the sum of w(v)w(v) over all v∈V(F)v\in V(F). The minimum weight of a fractional vertex cover of FF is denoted by τ∗(F)\tau^*(F).

Lemma 2.1 (Fractional matching–cover duality, see, e.g., [8]). For every hypergraph FF, we have

ν∗(F)=τ∗(F).\nu^*(F)=\tau^*(F).

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 0=X0,…,Xm0=X_0,\ldots,X_m be a martingale satisfying ∣Xi+1−Xi∣≤1|X_{i+1}-X_i|\le1 for every integer 0≤i<m0\le i<m. For every λ>0\lambda>0 we have

P(∣Xm∣>λm)<2exp⁡(−λ22).\mathbb{P}(|X_m|>\lambda\sqrt{m})<2\exp\left(-\frac{\lambda^2}{2}\right).

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 diam⁡∞\operatorname{diam}_{\infty} for diameter in the ℓ∞\ell_{\infty} metric.

Lemma 2.3 (Clustering). For every integer q≥1q\ge1 and every η>0\eta>0, there exists ε>0\varepsilon>0 such that the following holds. Let VV be an nn-element set and let s≥1s\ge1 be an integer satisfying s<εns<\varepsilon n. Let ρ:V→[0,1]q\rho:V\to[0,1]^q. Put m=⌊n/s⌋m=\lfloor n/s\rfloor. There exists an equipartition V=V1∪⋯∪VmV=V_1\cup\cdots\cup V_m, with cluster sizes differing by at most 11, such that

1m∑i=1mdiam⁡∞(ρ(Vi))≤η.\frac{1}{m}\sum_{i=1}^{m}\operatorname{diam}_{\infty}(\rho(V_i))\le\eta.

Proof. Partition [0,1]q[0,1]^q into M=M(η,q)M=M(\eta,q) cubes W1,…,WMW_1,\ldots,W_M of side length at most η/2\eta/2. In each coordinate, use intervals closed on the left and open on the right, including 11 in the last interval. Choose an ordering of VV in which every element of ρ−1(Wa)\rho^{-1}(W_a) precedes every element of ρ−1(Wb)\rho^{-1}(W_b) whenever a<ba<b. Split this order into mm consecutive clusters V1,…,VmV_1,\ldots,V_m whose sizes differ by at most 11. At most MM clusters have images meeting more than one cube. ysady

If a cluster’s image lies in one cube, its ℓ∞\ell_{\infty} diameter is at most η/2\eta/2; otherwise it is at most 1. Since s<εns < \varepsilon n implies m>1/ε−1m > 1/\varepsilon- 1, choosing 0<ε<10 < \varepsilon< 1 sufficiently small ensures that M/m≤η/2M/m \le\eta/2. Therefore

1m∑i=1mdiam⁡∞(ρ(Vi))≤η2+Mm≤η,\frac{1}{m}\sum_{i=1}^{m}\operatorname{diam}_{\infty}(\rho(V_i)) \le\frac{\eta}{2}+\frac{M}{m}\le\eta,

as required.

Fractional matchings

In this section we prove the following fractional version of Theorem 1.2.

Theorem 3.1. For all integers r≥2r \ge2 and q≥1q \ge1 and every η>0\eta> 0, there exists ε>0\varepsilon> 0 such that the following holds. Let 1≤s≤n1 \le s \le n, let HH be an nn-vertex ss-connector rr-graph, let H=(H1,…,Hq)\mathcal{H}=(H_1,\ldots,H_q) be a qq-colouring of HH, and let t∈N+q\mathbf{t}\in\mathbb{N}^{q}_{+}. If s<εns < \varepsilon n and n≥AFL⁡r(t)+ηnn\ge\operatorname{AFL}_r(\mathbf{t})+\eta n, then there exists j∈[q]j\in[q] such that ν∗(Hj)≥tj\nu^*(H_j)\ge t_j.

The proof uses the following lemma that clusters vertices according to the fractional cover weights in each colour.

Lemma 3.2. For all integers r≥2r \ge2 and q≥1q \ge1 and every γ>0\gamma> 0, there exists ε>0\varepsilon> 0 such that the following holds. Let H1,…,HqH_1,\ldots,H_q be rr-graphs on a common nn-element vertex set VV, and let s≥1s\ge1 be an integer satisfying s<εns<\varepsilon n. Put m=⌊n/s⌋m=\lfloor n/s\rfloor. Then there exists an equipartition V=V1∪⋯∪VmV=V_1\cup\cdots\cup V_m with the following property. For every j∈[q]j\in[q], let Γj\Gamma_j be the rr-graph on [m][m] whose edges are the sets S∈([m]r)S\in\binom{[m]}{r} for which HjH_j has an edge meeting every ViV_i, i∈Si\in S, once. Then, for every j∈[q]j\in[q],

ν∗(Hj)≥sν∗(Γj)−γn.\nu^*(H_j)\ge s\nu^*(\Gamma_j)-\gamma n.

Proof. Choose ε>0\varepsilon>0 as in Lemma 2.3 for qq and γ\gamma. For every j∈[q]j\in[q], choose an optimal fractional vertex cover wjw_j of HjH_j. We may assume that wj(v)≤1w_j(v)\le1 for every v∈Vv\in V. Apply Lemma 2.3 to ρ(v)=(w1(v),…,wq(v))\rho(v)=(w_1(v),\ldots,w_q(v)) to obtain an equipartition V=V1∪⋯∪VmV=V_1\cup\cdots\cup V_m such that

1m∑i=1mdiam⁡∞(ρ(Vi))≤γ.\frac{1}{m}\sum_{i=1}^{m}\operatorname{diam}_{\infty}(\rho(V_i))\le\gamma.

For i∈[m]i\in[m] and j∈[q]j\in[q], put wj(i)=max⁡v∈Viwj(v)w_j(i)=\max_{v\in V_i}w_j(v). For every v∈Viv\in V_i, we have wj(i)≤wj(v)+diam⁡∞(ρ(Vi))w_j(i)\le w_j(v)+\operatorname{diam}_{\infty}(\rho(V_i)). Since wj(i)w_j(i) does not depend on vv,

wj(i)=1∣Vi∣∑v∈Viwj(i)≤1∣Vi∣∑v∈Vi(wj(v)+diam⁡∞(ρ(Vi))).w_j(i)=\frac{1}{|V_i|}\sum_{v\in V_i}w_j(i)\le\frac{1}{|V_i|}\sum_{v\in V_i}\bigl(w_j(v)+\operatorname{diam}_{\infty}(\rho(V_i))\bigr).

Summing over ii, using ∣Vi∣≥s|V_i|\ge s and ∑vwj(v)=ν∗(Hj)\sum_v w_j(v)=\nu^*(H_j) by Lemma 2.1, gives

∑i=1mwj(i)≤∑i=1m1∣Vi∣∑v∈Viwj(v)+∑i=1mdiam⁡∞(ρ(Vi))≤ν∗(Hj)s+∑i=1mdiam⁡∞(ρ(Vi))≤ν∗(Hj)s+γm.(1)\begin{aligned} \sum_{i=1}^{m}w_j(i)\le\sum_{i=1}^{m}\frac{1}{|V_i|}\sum_{v\in V_i}w_j(v)+\sum_{i=1}^{m}\operatorname{diam}_{\infty}(\rho(V_i)) \\ &\le\frac{\nu^*(H_j)}{s}+\sum_{i=1}^{m}\operatorname{diam}_{\infty}(\rho(V_i))\le\frac{\nu^*(H_j)}{s}+\gamma m. \tag*{(1)} \end{aligned}

Fix j∈[q]j \in[q]. For every edge SS of Γj\Gamma_j, choose an edge ee of HjH_j meeting every ViV_i, i∈Si \in S, once. Since wjw_j is a fractional vertex cover of HjH_j,

∑i∈Swj(i)≥∑v∈ewj(v)≥1.\sum_{i\in S} w_j(i) \ge\sum_{v\in e} w_j(v) \ge1.

Thus the weights wj(i)w_j(i) form a fractional vertex cover of Γj\Gamma_j. By Lemma 2.1 and (1),

ν∗(Γj)≤∑i=1mwj(i)≤ν∗(Hj)s+γm.\nu^*(\Gamma_j) \le\sum_{i=1}^{m} w_j(i) \le\frac{\nu^*(H_j)}{s}+\gamma m.

Rearranging gives ν∗(Hj)≥sν∗(Γj)−γsm≥sν∗(Γj)−γn\nu^*(H_j) \ge s\nu^*(\Gamma_j)-\gamma sm \ge s\nu^*(\Gamma_j)-\gamma n, as required.

We now deduce Theorem 3.1. We use the following properties that are immediate from the definition of AFL⁡r\operatorname{AFL}_r. Fix integers r≥2r \ge2 and q≥1q \ge1. Write 1q=(1,…,1)∈Nq\mathbf{1}_q=(1,\ldots,1)\in\mathbb{N}^q. For t∈N+q\mathbf{t}\in\mathbb{N}_+^q and every integer b≥0b\ge0, we have

AFL⁡r(t+b1q)=AFL⁡r(t)+(r+q−1)b.(2)\operatorname{AFL}_r(\mathbf{t}+b\mathbf{1}_q)=\operatorname{AFL}_r(\mathbf{t})+(r+q-1)b. \tag*{(2)}

If t,k∈N+q\mathbf{t},\mathbf{k}\in\mathbb{N}_+^q and 0<θ≤10<\theta\le1 satisfy kj≤θtjk_j\le\theta t_j for every j∈[q]j\in[q], then

AFL⁡r(k)≤θAFL⁡r(t)+(q−1)(θ−1)≤θAFL⁡r(t).(3)\operatorname{AFL}_r(\mathbf{k})\le\theta\operatorname{AFL}_r(\mathbf{t})+(q-1)(\theta-1)\le\theta\operatorname{AFL}_r(\mathbf{t}). \tag*{(3)}

Proof of Theorem 3.1. Put d=r+q−1d=r+q-1 and γ=η/(4d)\gamma=\eta/(4d). For these rr, qq and γ\gamma, let ε0>0\varepsilon_0>0 be supplied by Lemma 3.2. Put ε=min⁡{ε0,γ,η/(2(d+1))}\varepsilon=\min\{\varepsilon_0,\gamma,\eta/(2(d+1))\}. Put m=⌊n/s⌋m=\lfloor n/s\rfloor and b=⌈2γn⌉b=\lceil2\gamma n\rceil. Since b≤2γn+1b\le2\gamma n+1, s≥1s\ge1 and 2dγ=η/22d\gamma=\eta/2, we have

db+s≤2dγn+d+s≤ηn/2+(d+1)s.db+s\le2d\gamma n+d+s\le\eta n/2+(d+1)s.

Moreover, s<εns<\varepsilon n and ε≤η/(2(d+1))\varepsilon\le\eta/(2(d+1)) give (d+1)s<ηn/2(d+1)s<\eta n/2, so db+s<ηndb+s<\eta n. Using n≥AFL⁡r(t)+ηnn\ge\operatorname{AFL}_r(\mathbf{t})+\eta n and (2), we obtain

AFL⁡r(t+b1q)=AFL⁡r(t)+db≤n−ηn+db<n−s≤sm,\operatorname{AFL}_r(\mathbf{t}+b\mathbf{1}_q)=\operatorname{AFL}_r(\mathbf{t})+db\le n-\eta n+db<n-s\le sm,

where the last inequality follows from m=⌊n/s⌋>n/s−1m=\lfloor n/s\rfloor>n/s-1. Apply Lemma 3.2 to H1,…,HqH_1,\ldots,H_q. The resulting graphs form a qq-colouring Γ=(Γ1,…,Γq)\Gamma=(\Gamma_1,\ldots,\Gamma_q) of KmrK_m^r, since HH is an ss-connector. Put kj=⌊(tj+b)/s⌋k_j=\lfloor(t_j+b)/s\rfloor for every j∈[q]j\in[q] and k=(k1,…,kq)\mathbf{k}=(k_1,\ldots,k_q). Since b≥2γn>2sb\ge2\gamma n>2s, every kjk_j is positive. Applying (3) with θ=1/s\theta=1/s and t+b1q\mathbf{t}+b\mathbf{1}_q in place of t\mathbf{t} gives

AFL⁡r(k)≤1sAFL⁡r(t+b1q)≤m.\operatorname{AFL}_r(\mathbf{k})\le\frac{1}{s}\operatorname{AFL}_r(\mathbf{t}+b\mathbf{1}_q)\le m.

By Theorem 1.1, some Γj\Gamma_j has a matching of size kjk_j. For this jj, Lemma 3.2 and s<γns<\gamma n give

ν∗(Hj)≥sν∗(Γj)−γn≥skj−γn≥tj+b−s−γn≥tj.\nu^*(H_j)\ge s\nu^*(\Gamma_j)-\gamma n\ge sk_j-\gamma n\ge t_j+b-s-\gamma n\ge t_j.

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 jj to a single global choice of j0j_0.

Theorem 4.1 (Local-to-global, fractional-to-integral). For all integers r≥2r \ge2 and q≥1q \ge1 and every γ>0\gamma> 0, there exist 0<δ≤10 < \delta\le1 and ℓ0∈N\ell_0 \in\mathbb{N} such that the following holds. Let nn and ℓ\ell be positive integers satisfying ℓ0≤ℓ<δn\ell_0 \le\ell< \delta n, let H1,…,HqH_1,\ldots,H_q be rr-graphs on a common nn-element vertex set VV, and let β=(β1,…,βq)∈[0,1/r]q\boldsymbol{\beta} = (\beta_1,\ldots,\beta_q) \in[0,1/r]^q. Suppose that, for every U∈(Vℓ)U \in\binom{V}{\ell}, there exists j∈[q]j \in[q] such that ν∗(Hj[U])≥βjℓ\nu^*(H_j[U]) \ge\beta_j\ell. Then there exists j0∈[q]j_0 \in[q] such that

ν(Hj0)≥(βj0−γ)n.\nu(H_{j_0}) \ge(\beta_{j_0}-\gamma)n.

We will address point (a) via the following matching theorem due to Kahn. For a fractional matching xx in a hypergraph FF, put

α(x)=max⁡u,v∈V(F)u≠v∑e∈E(F){u,v}⊆ex(e).\alpha(x) = \max_{\substack{u,v\in V(F)\\u\ne v}} \sum_{\substack{e\in E(F)\\\{u,v\}\subseteq e}} x(e).

Theorem 4.2 ([23 Theorem 1.2(a)]). For every integer r≥2r \ge2 and every γ>0\gamma> 0, there exists 0<δ≤10 < \delta\le1 such that, if FF is a hypergraph whose edges have size at most rr and xx is a fractional matching in FF with α(x)<δ\alpha(x) < \delta, then

ν(F)≥(1−γ)∑e∈E(F)x(e).\nu(F) \ge(1-\gamma)\sum_{e\in E(F)}x(e).

We will address point (b) via the following application of Azuma’s inequality, which provides a single colour j0j_0 with a fractional matching suitable for applying Theorem 4.2.

Lemma 4.3. For all integers r≥2r \ge2 and q≥1q \ge1 and every γ>0\gamma> 0, there exists ℓ0∈N\ell_0 \in\mathbb{N} such that the following holds. Let ℓ0≤ℓ<n\ell_0 \le\ell< n, let H1,…,HqH_1,\ldots,H_q be rr-graphs on a common nn-element vertex set VV, and let β=(β1,…,βq)∈[0,1/r]q\boldsymbol{\beta} = (\beta_1,\ldots,\beta_q) \in[0,1/r]^q. Suppose that, for every U∈(Vℓ)U \in\binom{V}{\ell}, there exists j∈[q]j \in[q] such that ν∗(Hj[U])≥βjℓ\nu^*(H_j[U]) \ge\beta_j\ell. Then there exist j0∈[q]j_0 \in[q] and a fractional matching xx in Hj0H_{j_0} such that α(x)≤(ℓ−1)/(n−1)\alpha(x) \le(\ell-1)/(n-1) and

∑e∈E(Hj0)x(e)≥(βj0−γ)n.\sum_{e\in E(H_{j_0})}x(e) \ge(\beta_{j_0}-\gamma)n.

The averaging argument in the proof below is similar to that of Alon, Frankl, Huang, Rödl, Ruciński and Sudakov [1].

Proof. Choose ℓ0\ell_0 sufficiently large that, for every ℓ≥ℓ0\ell\ge\ell_0, 2qexp⁡(−γ2ℓ/2)<12q\exp(-\gamma^2\ell/2) < 1. Let UU be chosen uniformly from (Vℓ)\binom{V}{\ell}. For j∈[q]j \in[q] and U∈(Vℓ)U \in\binom{V}{\ell}, put fj(U)=ν∗(Hj[U])f_j(U) = \nu^*(H_j[U]) and μj=Efj(U)\mu_j = \mathbb{E}f_j(U). We will show that fj(U)f_j(U) is concentrated about its mean μj\mu_j. To this end, we apply Azuma’s inequality. Fix j∈[q]j \in[q] and order the vertices of UU uniformly at random as v1,…,vℓv_1,\ldots,v_\ell. For 0≤k≤ℓ0 \le k \le\ell, put

Xk=E[fj(U)∣v1,…,vk]−μj.X_k = \mathbb{E}\left[f_j(U)\mid v_1,\ldots,v_k\right]-\mu_j.

Then (Xk)k=0ℓ(X_k)_{k=0}^{\ell} is a martingale with X0=0X_0=0 and Xℓ=fj(U)−μjX_\ell=f_j(U)-\mu_j.

We need to check that ∣Xk−Xk−1∣≤1|X_k-X_{k-1}| \le1 for 1≤k≤ℓ1 \le k \le\ell. Fix v1,…,vk−1v_1,\ldots,v_{k-1} and put W=V∖{v1,…,vk−1}W=V\setminus\{v_1,\ldots,v_{k-1}\}. For v∈Wv\in W, write g(v)=E[fj(U)∣v1,…,vk−1,vk=v]g(v)=\mathbb{E}\left[f_j(U)\mid v_1,\ldots,v_{k-1},v_k=v\right]. We first show that ∣g(u)−g(v)∣≤1|g(u)-g(v)|\le1 for any u,v∈Wu,v\in W. Pair each possible final set UU when vk=uv_k=u with UU itself if v∈Uv\in U, and with (U∖{u})∪{v}(U\setminus\{u\})\cup\{v\} 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 UU changes fj(U)f_j(U) by at most 1, since deleting from a fractional matching all edges through the removed vertex loses weight at most 1. Thus ∣g(u)−g(v)∣≤1|g(u)-g(v)| \le1. Before vkv_k is exposed, each vertex of WW is equally likely to be chosen, so

∣Xk−Xk−1∣=∣g(vk)−1∣W∣∑v∈Wg(v)∣≤1∣W∣∑v∈W∣g(vk)−g(v)∣≤1.|X_k-X_{k-1}|=\left|g(v_k)-\frac{1}{|W|}\sum_{v\in W}g(v)\right|\le\frac{1}{|W|}\sum_{v\in W}|g(v_k)-g(v)|\le1.

Applying Lemma 2.2 gives

P(∣fj(U)−μj∣>γℓ)<2exp⁡(−γ2ℓ2).\mathbb{P}\left(|f_j(U)-\mu_j|>\gamma\ell\right)<2\exp\left(-\frac{\gamma^2\ell}{2}\right).

By the union bound over all j∈[q]j\in[q] and the choice of ℓ0\ell_0,

P(∃j∈[q]:∣fj(U)−μj∣>γℓ)<2qexp⁡(−γ2ℓ/2)<1.\mathbb{P}\left(\exists j\in[q]: |f_j(U)-\mu_j|>\gamma\ell\right)<2q\exp(-\gamma^2\ell/2)<1.

Hence there exists an ℓ\ell-set U0U_0 such that ∣fj(U0)−μj∣≤γℓ|f_j(U_0)-\mu_j|\le\gamma\ell for every j∈[q]j\in[q]. By the hypothesis of the lemma, there exists j0∈[q]j_0\in[q] such that fj0(U0)≥βj0ℓf_{j_0}(U_0)\ge\beta_{j_0}\ell. Thus μj0≥fj0(U0)−γℓ≥(βj0−γ)ℓ\mu_{j_0}\ge f_{j_0}(U_0)-\gamma\ell\ge(\beta_{j_0}-\gamma)\ell.

For every ℓ\ell-set UU, choose an optimal fractional matching xUx_U in Hj0[U]H_{j_0}[U], and put xU(e)=0x_U(e)=0 for every edge ee of Hj0H_{j_0} not contained in UU. For every e∈E(Hj0)e\in E(H_{j_0}), put

x(e)=nℓExU(e).x(e)=\frac{n}{\ell}\mathbb{E}x_U(e).

For every v∈Vv\in V,

∑e∋vx(e)=nℓE∑e∋vxU(e)≤nℓP(v∈U)=1,\sum_{e\ni v}x(e)=\frac{n}{\ell}\mathbb{E}\sum_{e\ni v}x_U(e)\le\frac{n}{\ell}\mathbb{P}(v\in U)=1,

so xx is a fractional matching in Hj0H_{j_0}. Moreover,

∑e∈E(Hj0)x(e)=nℓμj0≥(βj0−γ)n.\sum_{e\in E(H_{j_0})}x(e)=\frac{n}{\ell}\mu_{j_0}\ge(\beta_{j_0}-\gamma)n.

Finally,

α(x)=max⁡u,v∈Vu≠v∑e⊇{u,v}x(e)≤nℓmax⁡u,v∈Vu≠vP({u,v}⊆U)=ℓ−1n−1.\alpha(x)=\max_{\substack{u,v\in V\\u\ne v}}\sum_{e\supseteq\{u,v\}}x(e)\le\frac{n}{\ell}\max_{\substack{u,v\in V\\u\ne v}}\mathbb{P}(\{u,v\}\subseteq U)=\frac{\ell-1}{n-1}.

We conclude this section with the proof of its main result.

Proof of Theorem 4.1. It suffices to consider 0<γ≤10<\gamma\le1. Apply Theorem 4.2 with γ2\frac{\gamma}{2} in place of γ\gamma, and let 0<δ≤10<\delta\le1 be the resulting constant. Apply Lemma 4.3 with γ2\frac{\gamma}{2} in place of γ\gamma, and let ℓ0∈N\ell_0\in\mathbb{N} be the resulting constant.

By Lemma 4.3, there exist j0∈[q]j_0\in[q] and a fractional matching xx in Hj0H_{j_0} such that

∑e∈E(Hj0)x(e)≥(βj0−γ2)n\sum_{e\in E(H_{j_0})}x(e)\ge\left(\beta_{j_0}-\frac{\gamma}{2}\right)n

and α(x)≤(ℓ−1)/(n−1)<ℓ/n<δ\alpha(x)\le(\ell-1)/(n-1)<\ell/n<\delta. By Theorem 4.2 and βj0≤1/r≤1\beta_{j_0}\le1/r\le1, we have

ν(Hj0)≥(1−γ2)(βj0−γ2)n≥(βj0−γ)n.\nu(H_{j_0})\ge\left(1-\frac{\gamma}{2}\right)\left(\beta_{j_0}-\frac{\gamma}{2}\right)n\ge(\beta_{j_0}-\gamma)n.

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 η<1\eta< 1. Put d=r+q−1d=r+q-1 and γ=η/(8d)\gamma=\eta/(8d). For these rr, qq and γ\gamma, let 0<δ≤10<\delta\leq1 and ℓ0∈N\ell_0\in\mathbb{N} be supplied by Theorem 4.1, and let ε0>0\varepsilon_0>0 be supplied by Lemma 3.2. Put

ε=min⁡{δ2(ℓ0+1),δε02,δγ4,η2d}.\varepsilon=\min\left\{\frac{\delta}{2(\ell_0+1)},\frac{\delta\varepsilon_0}{2},\frac{\delta\gamma}{4},\frac{\eta}{2d}\right\}.

Let H=(V,E)H=(V,E) and t\mathbf{t} satisfy the assumptions of Theorem 1.2, and fix a qq-colouring H=(H1,…,Hq)\mathcal{H}=(H_1,\ldots,H_q) of HH. Put ℓ=⌈δn⌉−1\ell=\lceil\delta n\rceil-1 and m=⌊ℓ/s⌋m=\lfloor\ell/s\rfloor. Since 1≤s<εn1\leq s<\varepsilon n, we have n>1/εn>1/\varepsilon. By our choice of ε\varepsilon, we have δn/2>δ/(2ε)≥ℓ0+1\delta n/2>\delta/(2\varepsilon)\geq\ell_0+1, so ℓ0≤δn/2≤ℓ<δn\ell_0\leq\delta n/2\leq\ell<\delta n. Our choice of ε\varepsilon also gives s<εn≤δε0n/2≤ε0ℓs<\varepsilon n\leq\delta\varepsilon_0n/2\leq\varepsilon_0\ell. Moreover, s<εn≤δγn/4≤γℓ/2s<\varepsilon n\leq\delta\gamma n/4\leq\gamma\ell/2, and hence m>ℓ/s−1>2/γ−1≥1/γm>\ell/s-1>2/\gamma-1\geq1/\gamma. Finally, d≤η/(2ε)<ηn/2d\leq\eta/(2\varepsilon)<\eta n/2.

Put b=⌈4γn⌉b=\lceil4\gamma n\rceil, so db≤4dγn+d=ηn/2+d<ηndb\leq4d\gamma n+d=\eta n/2+d<\eta n. Put t+=t+b1q\mathbf{t}^{+}=\mathbf{t}+b\mathbf{1}_q and βj=(tj+b)/n\beta_j=(t_j+b)/n. By (2) and the hypothesis n≥AFL⁡r(t)+ηnn\geq\operatorname{AFL}_r(\mathbf{t})+\eta n, we have AFL⁡r(t+)=AFL⁡r(t)+db≤n−ηn+db<n\operatorname{AFL}_r(\mathbf{t}^{+})=\operatorname{AFL}_r(\mathbf{t})+db\leq n-\eta n+db<n.

For every j∈[q]j\in[q], the definition of AFL⁡r\operatorname{AFL}_r gives

n>AFL⁡r(t+)=(r−1)∥t+∥∞+(tj+b)+∑i≠j(ti+b−1)≥r(tj+b).n>\operatorname{AFL}_r(\mathbf{t}^{+})=(r-1)\lVert\mathbf{t}^{+}\rVert_\infty+(t_j+b)+\sum_{i\neq j}(t_i+b-1)\geq r(t_j+b).

since ∥t+∥∞≥tj+b\lVert\mathbf{t}^{+}\rVert_\infty\geq t_j+b and every summand is nonnegative. Thus 4γ≤b/n≤βj<1/r4\gamma\leq b/n\leq\beta_j<1/r for every j∈[q]j\in[q]. Put kj=⌊βjm⌋k_j=\lfloor\beta_jm\rfloor for every j∈[q]j\in[q] and k=(k1,…,kq)\mathbf{k}=(k_1,\ldots,k_q). Since βjm≥4\beta_jm\geq4, every kjk_j is positive. Applying (3) with θ=m/n\theta=m/n and t+\mathbf{t}^{+} in place of t\mathbf{t} gives

AFL⁡r(k)≤mnAFL⁡r(t+)<m.\operatorname{AFL}_r(\mathbf{k})\leq\frac{m}{n}\operatorname{AFL}_r(\mathbf{t}^{+})<m.

For every U∈(Vℓ)U\in\binom{V}{\ell}, apply Lemma 3.2 to H1[U],…,Hq[U]H_1[U],\ldots,H_q[U]. The resulting graphs form a qq-colouring Γ=(Γ1,…,Γq)\Gamma=(\Gamma_1,\ldots,\Gamma_q) of KmrK_m^r, since H[U]H[U] is an ss-connector. By Theorem 1.1, there exists j=j(U)∈[q]j=j(U)\in[q] such that Γj\Gamma_j has a matching of size kjk_j. Since m>1/γm>1/\gamma, we have ν(Γj)≥kj≥βjm−1≥(βj−γ)m\nu(\Gamma_j)\geq k_j\geq\beta_jm-1\geq(\beta_j-\gamma)m.

Since sm≥ℓ−ssm\geq\ell-s, 0≤βj−γ≤10\leq\beta_j-\gamma\leq1 and s<γℓs<\gamma\ell, Lemma 3.2 gives

ν∗(Hj[U])≥s(βj−γ)m−γℓ≥(βj−γ)(ℓ−s)−γℓ=(βj−2γ)ℓ−(βj−γ)s≥(βj−2γ)ℓ−s>(βj−3γ)ℓ.\begin{aligned} \nu^*(H_j[U])&\geq s(\beta_j-\gamma)m-\gamma\ell\\ &\geq(\beta_j-\gamma)(\ell-s)-\gamma\ell\\ &=(\beta_j-2\gamma)\ell-(\beta_j-\gamma)s\\ &\geq(\beta_j-2\gamma)\ell-s>(\beta_j-3\gamma)\ell. \end{aligned}

Thus Theorem 4.1, with βj−3γ\beta_j-3\gamma in place of βj\beta_j, gives some j∈[q]j\in[q] such that

ν(Hj)≥(βj−4γ)n=tj+b−4γn≥tj.\nu(H_j)\geq(\beta_j-4\gamma)n=t_j+b-4\gamma n\geq t_j.

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 r≥2r\geq2 and every α>0\alpha>0, there exists C>0C>0 such that the following holds. Let nn and ss be positive integers satisfying 2s≤αn2s\leq\alpha n, let HH be an nn-vertex ss-connector rr-graph, and let HpH_p be obtained from HH by retaining each edge independently with probability p≥C(s/n)−1p\geq C(s/n)^{-1}. With probability at least 1−e−n1-e^{-n}, HpH_p is a ⌈αn⌉\lceil\alpha n\rceil-connector.

Proof. Put c=(α/2)rc=(\alpha/2)^r and choose C>0C>0 such that cC≥log⁡(r+1)+1cC\ge\log(r+1)+1. Put a=⌈αn⌉a=\lceil\alpha n\rceil. Fix pairwise disjoint aa-sets A1,…,ArA_1,\ldots,A_r. We want HpH_p to contain an edge meeting each AiA_i once. To this end, we first find many such edges in HH. Partition each of A1,…,Ar−1A_1,\ldots,A_{r-1} into ⌊a/s⌋\lfloor a/s\rfloor disjoint ss-sets, ignoring the remaining vertices. For each i∈[r−1]i\in[r-1], choose one of these ss-sets inside AiA_i and call it BiB_i. For each v∈Arv\in A_r, look for an edge consisting of vv and one vertex from each BiB_i. Such an edge can be absent for at most s−1s-1 vertices: ss of them together with B1,…,Br−1B_1,\ldots,B_{r-1} would contradict the connector property. Choosing one edge for each of the other vertices gives at least a−s+1a-s+1 distinct edges. Each chosen edge has exactly one vertex in each AiA_i. For each i∈[r−1]i\in[r-1], its vertex in AiA_i lies in exactly one of the disjoint ss-sets, so this vertex determines BiB_i. Hence no edge is counted for two different choices of B1,…,Br−1B_1,\ldots,B_{r-1}. Since a≥αn≥2sa\ge\alpha n\ge2s, we have a−s+1≥a/2a-s+1\ge a/2 and ⌊a/s⌋≥a/s−1≥a/(2s)\lfloor a/s\rfloor\ge a/s-1\ge a/(2s). The number of edges of HH meeting every AiA_i once is therefore at least

(a−s+1)⌊a/s⌋r−1≥a2(a2s)r−1=ar2rsr−1≥cnrsr−1.(a-s+1)\lfloor a/s\rfloor^{r-1}\ge\frac{a}{2}\left(\frac{a}{2s}\right)^{r-1}=\frac{a^r}{2^r s^{r-1}}\ge\frac{cn^r}{s^{r-1}}.

Using p≥C(s/n)r−1p\ge C(s/n)^{r-1}, the probability that none of these edges survives is at most

exp⁡(−pcnrsr−1)≤exp⁡(−cCn).\exp\left(-\frac{pcn^r}{s^{r-1}}\right)\le\exp(-cCn).

There are at most (r+1)n(r+1)^n choices of the disjoint sets A1,…,ArA_1,\ldots,A_r, since each vertex lies in one of these rr sets or outside their union. By the union bound, the probability that HpH_p is not an aa-connector is at most

(r+1)ne−cCn=exp⁡((log⁡(r+1)−cC)n)≤e−n,(r+1)^n e^{-cCn}=\exp((\log(r+1)-cC)n)\le e^{-n},

where the last inequality uses cC≥log⁡(r+1)+1cC\ge\log(r+1)+1.

Proof of Theorem 1.3. Let 0<ε≤10<\varepsilon\le1 be the constant supplied by Theorem 1.2 for rr, qq and η\eta. Put α=ε/2\alpha=\varepsilon/2, and let C>0C>0 be supplied by Lemma 5.1 for rr and α\alpha. We may assume that C≥(2/α)r−1C\ge(2/\alpha)^{r-1}. Since C(s/n)r−1≤p≤1C(s/n)^{r-1}\le p\le1, we have s≤C−1/(r−1)n≤αn/2s\le C^{-1/(r-1)}n\le\alpha n/2. In particular, 2s≤αn2s\le\alpha n and, since s≥1s\ge1, αn≥2\alpha n\ge2. Thus ⌈αn⌉≤αn+1<2αn=εn\lceil\alpha n\rceil\le\alpha n+1<2\alpha n=\varepsilon n. Lemma 5.1 implies that, with probability at least 1−e−n1-e^{-n}, HpH_p is a ⌈αn⌉\lceil\alpha n\rceil-connector. On this event, Theorem 1.2 gives Hp→tKr(r)H_p\to tK_r^{(r)} simultaneously for all t∈N+qt\in\mathbb{N}_+^q satisfying n≥AFL⁡r(t)+ηnn\ge\operatorname{AFL}_r(t)+\eta n.

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 rr has a perfect matching. We use the following perfect-matching theorem of Johansson, Kahn and Vu [22].

Theorem 5.2 ([22]). For every integer r≥2r\ge2, there exists A>0A>0 such that, whenever r∣mr\mid m and p≥Am1−rlog⁡mp\ge A m^{1-r}\log m, the random rr-graph G(r)(m,p)G^{(r)}(m,p) 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 r≥3r\ge3 and every α>0\alpha>0, there exists C>0C>0 such that, if p≥Cn2−rlog⁡np\ge Cn^{2-r}\log n and G∼G(r)(n,p)G\sim G^{(r)}(n,p), then whp G[W]G[W] contains a perfect matching for every W⊆[n]W\subseteq[n] satisfying ∣W∣≥αn|W|\ge\alpha n and r∣∣W∣r\mid|W|.

Proof. Let AA be the constant supplied by Theorem 5.2, and take C>Aα1−rC>A\alpha^{1-r}. Choose an integer ff with 1≪f≪n1\ll f\ll n, and put n′=n+fn'=n+f and p0=p/n′p_0=p/n', and let F1,…,Fn′F_1,\ldots,F_{n'} be independent copies of G(r)(n,p0)G^{(r)}(n,p_0) on the same vertex set. Fix W⊆[n]W\subseteq[n] with w=∣W∣≥αnw=|W|\ge\alpha n and r∣wr\mid w. Since n′/n→1n'/n\to1, our choice of CC gives p0≥Aα1−rn1−rlog⁡n≥Aw1−rlog⁡wp_0 \ge A\alpha^{1-r}n^{1-r}\log n \ge Aw^{1-r}\log w for all sufficiently large nn. By Theorem 5.2, each Fi[W]F_i[W] has a perfect matching with probability at least 12\frac{1}{2}. Hence the probability that none of F1[W],…,Fn′[W]F_1[W],\ldots,F_{n'}[W] has a perfect matching is at most 2−n′2^{-n'}. Put F=F1∪⋯∪Fn′F=F_1\cup\cdots\cup F_{n'}. By the union bound over the at most 2n2^n choices of W⊆[n]W\subseteq[n] with ∣W∣≥αn|W|\ge\alpha n and r∣∣W∣r\mid|W|, the probability that F[W]F[W] has no perfect matching for some such WW is at most 2n−n′=o(1)2^{n-n'}=o(1). The union FF has the distribution of G(r)(n,p′)G^{(r)}(n,p'), where p′=1−(1−p0)n′≤n′p0=pp'=1-(1-p_0)^{n'}\le n'p_0=p. Coupling with GG completes the proof.

Proof of Proposition 1.4. Put d=r+q−1d=r+q-1 and t=⌈(1−μ)n/d⌉t=\lceil(1-\mu)n/d\rceil. Choose 0<ε<1/r0<\varepsilon<1/r as in Theorem 1.2 for η=μ/2\eta=\mu/2, and put s=⌈εn/2⌉s=\lceil\varepsilon n/2\rceil. The definition of AFL⁡r\operatorname{AFL}_r gives

AFL⁡r(t1q)=(r−1)t+q(t−1)+1=dt−q+1≤dt.\operatorname{AFL}_r(t1_q)=(r-1)t+q(t-1)+1=dt-q+1\le dt.

Since t≤(1−μ)n/d+1t\le(1-\mu)n/d+1, for all sufficiently large nn we have s<εns<\varepsilon n and

dt+μn2≤(1−μ)n+d+μn2=(1−μ/2)n+d≤n.dt+\frac{\mu n}{2}\le(1-\mu)n+d+\frac{\mu n}{2}=(1-\mu/2)n+d\le n.

Thus n≥AFL⁡r(t1q)+μn/2n\ge\operatorname{AFL}_r(t1_q)+\mu n/2. Put α=(q−1)/(2d)\alpha=(q-1)/(2d), let C>0C>0 be supplied by Lemma 5.3 for rr and α\alpha, and let G∼G(r)(n,p)G\sim G^{(r)}(n,p) with p≥Cn2−rlog⁡np\ge Cn^{2-r}\log n. There are at most (r+1)n(r+1)^n ordered choices of pairwise disjoint sets A1,…,Ar⊆[n]A_1,\ldots,A_r\subseteq[n]. If each set has size at least ss, the probability that no edge meets them all is at most exp⁡(−psr)\exp(-ps^r). Since (r+1)nexp⁡(−psr)=o(1)(r+1)^n\exp(-ps^r)=o(1), a union bound shows that GG is an ss-connector whp. By Lemma 5.3, whp G[W]G[W] also has a perfect matching for every W⊆[n]W\subseteq[n] with ∣W∣≥αn|W|\ge\alpha n and r∣∣W∣r\mid|W|.

Fix a graph GG with both properties and an arbitrary qq-colouring of GG. By Theorem 1.2, there exists a monochromatic matching M1M_1 of size tt; if necessary, discard edges so that its size is exactly tt. Put W=[n]∖V(M1)W=[n]\setminus V(M_1). Then r∣∣W∣r\mid|W| and, for all sufficiently large nn,

∣W∣=n−rt≥q−1dn−r≥αn.|W|=n-rt\ge\frac{q-1}{d}n-r\ge\alpha n.

Hence G[W]G[W] has a perfect matching M2M_2. The union M1∪M2M_1\cup M_2 is a perfect matching and contains at least t≥(1−μ)n/dt\ge(1-\mu)n/d edges of one colour.

The extra factor nn over the perfect-matching threshold comes from the n′∼nn'\sim n independent copies of G(r)(n,p/n′)G^{(r)}(n,p/n') 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 H→tK2qH\to tK_2^q for every nn-vertex ss-connector graph HH whenever n≥AFL⁡2(t)+7(q+1)(s−1)n\ge\operatorname{AFL}_2(t)+7(q+1)(s-1). For t=(t1,…,tq)∈N+qt=(t_1,\ldots,t_q)\in\mathbb{N}_+^q, let Rsr(t)R_s^r(t) be the least nn such that every qq-colouring of every nn-vertex ss-connector rr-graph contains a colour-jj matching of size tjt_j for some j∈[q]j\in[q]. In this notation, the result of Niu and Wang [28] states that

Rs2(t)=Λt+max⁡{2s,∥t∥∞+s}.R_s^2(t)=\Lambda_t+\max\{2s,\lVert t\rVert_\infty+s\}.

This suggests the following analogue for rr-uniform hypergraphs:

Rsr(t)=?Λt+max⁡{rs,(r−1)∥t∥∞+s}.(4)R_s^r(t)\mathrel{\overset{?}{=}}\Lambda_t+\max\{rs,(r-1)\lVert t\rVert_\infty+s\}. \tag*{(4)}

However, this formula is false already for r=3r=3. To see this, let FF be the Fano plane, the Steiner triple system on seven vertices.

Proposition 6.1. The Fano plane FF is a 22-connector 33-graph and satisfies ν(F)=1\nu(F)=1.

Proof. Any two Fano lines meet, so ν(F)=1\nu(F)=1. To see the connector property, let A,B,CA,B,C be three pairwise disjoint pairs of Fano points, and let xx be the remaining point. There are four Fano lines avoiding xx. If none of them has one point in each of A,B,CA,B,C, 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 r=3r=3, s=2s=2 and t=(2,1)\mathbf{t}=(2,1), the right-hand side of (4) is 77. Colouring every edge of FF red gives a tK33\mathbf{t}K_3^3-free colouring of a 22-connector 33-graph on seven vertices, so R23(2,1)≥8R_2^3(2,1)\ge8.

The right-hand side of (4) is nevertheless a lower bound for Rsr(t)R_s^r(\mathbf{t}), as shown by the following two constructions.

  1. Consider disjoint sets BB of size rs−1rs-1 and SjS_j of size tj−1t_j-1 for j∈[q]j\in[q]. Every rr-set that meets S=⋃jSjS=\bigcup_j S_j is an edge, coloured by some jj for which it meets SjS_j.

  1. Label the colours so that t1=tmax⁡t_1=t_{\max}. Take the complete rr-graph on the disjoint union of sets B,S2,…,SqB,S_2,\ldots,S_q with ∣B∣=rt1−1|B|=rt_1-1 and ∣Sj∣=tj−1|S_j|=t_j-1 for 2≤j≤q2\le j\le q. Add s−1s-1 isolated vertices. Colour an edge with some j≥2j\ge2 if it meets SjS_j, and otherwise with colour 1.

Although (4) fails, it seems plausible that the additive error above AFL⁡r(t)\operatorname{AFL}_r(\mathbf{t}) should remain linear in ss, as in the r=2r=2 case. The following conjecture proposes such an interpolation between AFL⁡\operatorname{AFL} and Theorem 1.2 for the full range of ss.

Conjecture 6.2. For all integers r≥2r\ge2 and q≥1q\ge1, there exists C=C(r,q)>0C=C(r,q)>0 such that, for every integer s≥1s\ge1 and every t∈N+,\mathbf{t}\in\mathbb{N}_+,

Rsr(t)≤AFL⁡r(t)+C(s−1).R_s^r(\mathbf{t})\le\operatorname{AFL}_r(\mathbf{t})+C(s-1).

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. [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. [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. [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. [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. [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. [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. [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. [8]Claude Berge, Hypergraphs: Combinatorics of finite sets, North-Holland Mathematical Library, vol. 45, North-Holland, Amsterdam, 1989. ↑6
  9. [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. [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. [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. [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. [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. [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. [15]Asaf Ferber and Matthew Kwan, Almost all Steiner triple systems are almost resolvable, Forum of Mathematics, Sigma 8 (2020), e39, 24. ↑3DOI
  16. [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. [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. [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. [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. [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. [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. [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. [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. [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. [25]Shoham Letzter, Path Ramsey number for random graphs, Combinatorics, Probability and Computing 25 (2016), no. 4, 612–622. ↑3DOI
  26. [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. [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. [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. [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. [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. [31]Mathias Schacht, Extremal results for random discrete structures, Annals of Mathematics. Second Series 184 (2016), no. 2, 333–365. ↑2

Paper details

vlnc:W_ac2ejrb2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents