Clique counts under degree and matching constraints
math.CO, cs.DM
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the maximum number of t-cliques in graphs with maximum degree at most D and matching number at most M, with no restriction on the number of vertices.
Abstract
We study the maximum number of t-cliques in graphs with maximum degree at most D and matching number at most M, with no restriction on the number of vertices. For t at least 3, we determine this maximum whenever D at least 2M-1 and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for D at least 2M, while K 2M is uniquely extremal when D=2M-1. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even D. For fixed even D and 3 at most t at most D+1, every extremal graph consists, apart from isolated vertices, of copies of K D+1 together with a remainder whose order is bounded independently of M. When D/2 divides M, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality