Clique counts under degree and matching constraints

@misc{adak2026clique,
  title = {{Clique counts under degree and matching constraints}},
  author = {Rajat Adak},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01259},
  eprint = {2611.01259},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01259},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Clique counts under degree and matching constraints
AU  - Rajat Adak
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01259
UR  - https://arxiv.org/abs/2611.01259
AB  - 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≥ 3, we determine this maximum whenever D≥ 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≥ 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≤ t≤ 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.
ER  -