A generalised Ramsey–Turán problem for matchings
Peter Keevash, Peleg Michaeli · 2025
Read A generalised Ramsey–Turán problem for matchings by Peter Keevash, Peleg Michaeli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10679.txt.
Introduction
Peter Keevash and Peleg Michaeli prove a generalized Ramsey-Turán theorem for matchings in this 2025 paper. Ramsey theory asks how much structure a colored graph must contain. Turán theory asks how many pieces a graph can hold while avoiding a pattern. Their theorem fuses the two. The pattern is a matching, a set of disjoint edges. The setting spans many colors at once.
Take a graph whose edges are colored in q colors. Each color class is banned from containing a matching of a set size. The authors determine the most copies of any complete subgraph such a graph can hold. Two explicit constructions compete for that maximum. An intricate compression argument settles the contest. It builds on the Gallai-Edmonds decomposition of each color. One construction wins. The result extends two classics at once. They are the Cockayne-Lorimer theorem and the Erdős-Gallai theorem.
Catalog record
| CREATOR | Peter Keevash, Peleg Michaeli |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-10679
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A generalised Ramsey–Turán problem for matchings Peter Keevash, Peleg Michaeli Abstract We prove a generalised Ramsey–Turán theorem for matchings, which (a) simultaneously generalises the Cockayne–Lorimer Theorem (Ramsey for matchings) and the Erdős–Gallai Theorem (Turán for matchings), and (b) is a generalised Turán theorem in the sense that we can optimise the count of any clique (Turán-type theorems optimise the count of edges). More precisely, for integers q ≥ 1 q\geq 1 , n ≥ ℓ ≥ 2 n\geq\ell\geq 2 , and t 1 , … , t q ≥ 1 t_{1},\dots,t_{q}\geq 1 we determine the maximum number of ℓ \ell -vertex complete subgraphs in an n n -vertex graph that admits a q q -edge-colouring in which, for each j = 1 , … , q j=1,\dots,q , the j j -coloured subgraph has no matching of size t j t_{j} . We achieve this by identifying two explicit constructions and applying a compression argument to show that one of them achieves the maximum. Our compression algorithm is quite intricate and introduces methods that have not previously been applied to these types of problems: it employs an optimisation problem defined by the Gallai–Edmonds decompositions of each colour. 1 Introduction Extremal Combinatorics is a pillar of Discrete Mathematics with applications to many other fields, particularly Theoretical Computer Science, Geometry and Number Theory, see [ 21 ] . Many results of the field can be classified as Ramsey or Turán Theorems, which have a rich history dating to the early 20th century, see [ 7 , 17 , 14 , 18 ] . A hybrid of these two research directions proposed by Erdős and Sós in the 1960s is now known as Ramsey–Turán Theory, see [ 20 ] . Another generalisation of Turán problems, known simply as Generalised Turán Problems [ 12 ] , developed from a generalisation of Turán’s Theorem proved in the 1960s by Erdős [ 10 ] . Our paper concerns a common generalisation of Ramsey–Turán Theory and Generalised Turán Problems, which we will now define. Given graphs T and G , we write m_{T}(G) for the number of unlabelled copies of T in G . Given graphs H_{1},\dots,H_{q} , we write G\to(H_{1},\dots,H_{q}) if every q -edge-colouring of G has a j -coloured copy of H_{j} for some j\in[q]:=\{1,\dots,q\} . We define the Generalised Ramsey–Turán number by \mathbf{GRT}_{T}(n\to(H_{1},\dots,H_{q}))=\max\{m_{T}(G)\ :\ G\not\to(H_{1},\dots,H_{q}),\ |V(G)|=n\}. We also write m_{\ell}=m_{K_{\ell}} , \mathbf{GRT}_{\ell}=\mathbf{GRT}_{K_{\ell}} and tK_{2} for a matching of size t . Our first result is structural, showing that \mathbf{GRT}_{\ell}(n\to(t_{1}K_{2},\dots,t_{q}K_{2})) is achieved by a graph from a certain concrete family, which we will now define. Let G_{n,x,y} be an n -vertex graph on X\cup Y\cup Z , where X,Y,Z are pairwise disjoint, |X|=x and |Y|=y , and in which \{u,v\} is an edge if and only if either u,v\in X or \{u,v\}\cap Y\neq\varnothing . In other words, G_{n,x,y} is the join of K_{y} with the disjoint union of K_{x} and n-x-y isolated vertices. We call such G a clique-cone graph , with clique set X and cone set Y . Write \mathbb{N} for the set of nonnegative integers and \mathbb{N}_{+}=\mathbb{N}\smallsetminus\{0\} . For \mathbf{t}=(t_{1},\dots,t_{q})\in\mathbb{N}_{+}^{q} , we use \mathbf{t}K_{2} as an abbreviation for (t_{1}K_{2},\dots,t_{q}K_{2}) . 1.1 . For any integers n\geq\ell\geq 2 , q\geq 1 and \mathbf{t}\in\mathbb{N}_{+}^{q} , there exist 1\leq x\leq 2\|\mathbf{t}\|_{\infty}-1 and 0\leq y\leq n-x such that G_{n,x,y}\not\to\mathbf{t}K_{2} and m_{\ell}(G_{n,x,y})=\mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2}) . Our second theorem gives an explicit formula for \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2}) . We write m_{\ell}(G_{n,x,y})=\varphi_{\ell,n}(x,y)=\binom{x+y}{\ell}+\binom{y}{\ell-1}(n-x-y). (1) We also write \mathbf{1}_{q}=(1,\dots,1)\in\mathbb{N}_{+}^{q} and \Lambda_{\mathbf{t}}=\|\mathbf{t}-\mathbf{1}_{q}\|_{1}=\sum_{i=1}^{q}(t_{i}-1) for \mathbf{t}\in\mathbb{N}_{+}^{q} . 1.2 . For all \mathbf{t}\in\mathbb{N}_{+}^{q} and n\geq\max\{\ell,\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}}\} we have \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2})=\max\{\varphi_{\ell,n}(1,\Lambda_{\mathbf{t}}),\varphi_{\ell,n}(2\|\mathbf{t}\|_{\infty}-1,\Lambda_{\mathbf{t}}-\|\mathbf{t}\|_{\infty}+1)\}. Also, \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2})=0 for n<\ell and \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2})=\binom{n}{\ell} for \ell\leq n\leq\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}} . As discussed below, the \ell=2 case of this theorem simultaneously generalises the Erdős–Gallai Theorem (Turán for matchings) [ 9 ] and the Cockayne–Lorimer Theorem (Ramsey for matchings) [ 6 ] . In the non-trivial case n\geq\max\{\ell,\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}}\} , it identifies the extremal graph for \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2}) as G_{n,1,\Lambda_{\mathbf{t}}} or G_{n,2\|\mathbf{t}\|_{\infty}-1,\Lambda_{\mathbf{t}}-\|\mathbf{t}\|_{\infty}+1} , whichever yields a larger count of K_{\ell} ’s. For these to be candidate graphs G for \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2}) , we must also provide colourings demonstrating G\not\to\mathbf{t}K_{2} , which we do below, after some further definitions. A q -multi-colouring of a graph G=(V,E) is a sequence \mathcal{G}=(G_{1},\dots,G_{q}) where G_{j}=(V,E_{j}) is a simple graph for all j\in[q] , and \bigcup_{j}E_{j}=E . We call G the underlying graph of the coloured graph \mathcal{G} . An edge e is said to have colour j if e\in E_{j} . Note that we allow an edge to possess multiple colours and that in the definition of \mathbf{GRT} 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 q -multi-colourings as q -colourings . We say that \mathcal{G} is (H_{1},\dots,H_{q}) -free if G_{j} is H_{j} -free for all j\in[q] . The matching number \nu(G) of G is the size of a maximum matching in G . Write \nu(\mathcal{G})=(\nu(G_{1}),\dots,\nu(G_{q})) , and observe that G\not\to\mathbf{t}K_{2} if and only if there exists a q -colouring \mathcal{G} of G which is \mathbf{t}K_{2} -free, i.e. \nu(\mathcal{G})\leq\mathbf{t}-\mathbf{1}_{q} , with inequalities between vectors understood pointwise. (a) Sparse construction. (b) Dense construction. Figure 1 : Extremal constructions ( q=3 ). The thin dotted lines correspond to multi-coloured edges. Sparse construction Let \mathbf{t}=(t_{1},\dots,t_{q})\in\mathbb{N}_{+}^{q} and n\geq\max\{\ell,\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}}\} . Consider the following q -colouring \mathcal{G}=(G_{1},\dots,G_{q}) of G=G_{n,1,\Lambda_{\mathbf{t}}} . Partition the cone set Y into sets Y_{i} of size |Y_{i}|=t_{i}-1 for 1\leq i\leq q . We let each G_{i} consist of all edges incident to Y_{i} ; see Fig. 1(a) . Then m_{\ell}(G)=\varphi_{\ell,n}(1,\Lambda_{\mathbf{t}}) and \nu(\mathcal{G})\leq\mathbf{t}-\mathbf{1}_{q} , so G\not\to\mathbf{t}K_{2} . Dense construction Let \mathbf{t}=(t_{1},\dots,t_{q})\in\mathbb{N}_{+}^{q} and n\geq\max\{\ell,\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}}\} . Consider the following q -colouring \mathcal{G}=(G_{1},\dots,G_{q}) of G=G_{n,2\|\mathbf{t}\|_{\infty}-1,\Lambda_{\mathbf{t}}-\|\mathbf{t}\|_{\infty}+1} . Let X be the clique set and Y be the cone set. We assume without loss of generality that t_{q}=\|\mathbf{t}\|_{\infty} and partition Y into sets Y_{j} of size |Y_{j}|=t_{j}-1 for 1\leq j\leq q-1 . For 1\leq j\leq q-1 we let G_{j} consist of all edges incident to Y_{j} , and we let G_{q} consist of all edges contained in X ; see Fig. 1(b) . Then m_{\ell}(G)=\varphi_{\ell,n}(2\|\mathbf{t}\|_{\infty}-1,\Lambda_{\mathbf{t}}-\|\mathbf{t}\|_{\infty}+1) and \nu(\mathcal{G})\leq\mathbf{t}-\mathbf{1}_{q} , so G\not\to\mathbf{t}K_{2} . Note that the above two constructions do not depend on \ell , although which of them achieves \mathbf{GRT}_{\ell}(n\to\mathbf{t}K_{2}) does depend on \ell . When there is a single colour ( q=1 ) we obtain the two extremal constructions for the Erdős–Gallai Theorem [ 9 ] . When n=\|\mathbf{t}\|_{\infty}+\Lambda_{\mathbf{t}} we obtain a \mathbf{t}K_{2} -free q -colouring of K_{n} that is extremal for the Cockayne–Lorimer Theorem [ 6 ] ; this construction establishes the last statement in Theorem 1.2 . 1.1 Discussion and related results Let us place our result within the wider context of Turán, Ramsey, and Ramsey–Turán problems for matchings. The Turán number \ex(n,H) is the maximum number of edges in an H -free graph on n vertices. Thus \ex(n,H)=\mathbf{GRT}_{2}(n\to(H)) . The Erdős–Gallai Theorem [ 9 ] states that \mathbf{GRT}_{2}(n\to(tK_{2}))=\ex(n,tK_{2})=\max\left\{\varphi_{2,n}(1,t-1),\varphi_{2,n}(2t-1,0)\right\}. (2) This is the case q=1 , \ell=2 , \mathbf{t}=(t) of our formula in Theorem 1.2 . The generalised Turán number \ex(n,T,H) is the maximum number of unlabelled copies of T in an H -free graph on n vertices. Thus \ex(n,T,H)=\mathbf{GRT}_{T}(n\to(H)) . When T and H are cliques, this number was determined by Erdős [ 10 ] , thus generalising