2025/09/12 by Keevash, Peter, Michaeli, Peleg
#05C35 (Primary) #05C70 (Secondary) #05D10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.10679
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, n ≥ ℓ ≥ 2, and t1,…,tq ≥ 1 we determine the maximum number of ℓ-vertex complete subgraphs in an n-vertex graph that admits a q-edge-colouring in which, for each j=1,…,q, the j-coloured subgraph has no matching of size tj. 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.