





















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 \ge 1$, $n \ge \ell \ge 2$, and $t_1,\dots,t_q \ge 1$ we determine the maximum number of $\ell$-vertex complete subgraphs in an $n$-vertex graph that admits a $q$-edge-colouring in which, for each $j=1,\dots,q$, the $j$-coloured subgraph has no matching of size $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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。