A note on extremal constructions for the Erdős-Rademacher problem

被引:0
作者
Liu, Xizhi [1 ,2 ]
Pikhurko, Oleg [1 ,2 ]
机构
[1] Univ Warwick, Math Inst, Coventry, England
[2] Univ Warwick, DIMAP, Coventry, England
基金
欧洲研究理事会;
关键词
Erd & odblac; s-Rademacher problem; Lov & aacute; sz-Simonovits conjecture; Clique density theorem; TRIANGLES; NUMBER; DENSITY; GRAPHS;
D O I
10.1017/S0963548324000269
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
For given positive integers $r\ge 3$ , $n$ and $e\le \binom{n}{2}$ , the famous Erd & odblac;s-Rademacher problem asks for the minimum number of $r$ -cliques in a graph with $n$ vertices and $e$ edges. A conjecture of Lov & aacute;sz and Simonovits from the 1970s states that, for every $r\ge 3$ , if $n$ is sufficiently large then, for every $e\le \binom{n}{2}$ , at least one extremal graph can be obtained from a complete partite graph by adding a triangle-free graph into one part.In this note, we explicitly write the minimum number of $r$ -cliques predicted by the above conjecture. Also, we describe what we believe to be the set of extremal graphs for any $r\ge 4$ and all large $n$ , amending the previous conjecture of Pikhurko and Razborov.
引用
收藏
页数:11
相关论文
共 25 条
  • [1] On stability of the Erd's-Rademacher problem
    Balogh, Jozsef
    Clemen, Felix Christian
    [J]. ILLINOIS JOURNAL OF MATHEMATICS, 2023, 67 (01) : 1 - 11
  • [2] BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V79, P19, DOI 10.1017/S0305004100052063
  • [3] Eras P., 1955, RIVEON LEMATEMATIKA, V9, P13
  • [4] Erdos P., 1962, ILLINOIS J MATH, V6, P122
  • [5] LOWER BOUNDS ON THE NUMBER OF TRIANGLES IN A GRAPH
    FISHER, DC
    [J]. JOURNAL OF GRAPH THEORY, 1989, 13 (04) : 505 - 512
  • [6] Clique polynomials have a unique root of smallest modulus
    Goldwurm, M
    Santini, M
    [J]. INFORMATION PROCESSING LETTERS, 2000, 75 (03) : 127 - 132
  • [7] Goodman A W., 1959, AM MATH MONTHLY, V66, P778
  • [8] Kim J., 2020, Discrete Anal, V19, P26
  • [9] THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
    Liu, Hong
    Pikhurko, Oleg
    Staden, Katherine
    [J]. FORUM OF MATHEMATICS PI, 2020, 8
  • [10] On a generalized Erdos-Rademacher problem
    Liu, Xizhi
    Mubayi, Dhruv
    [J]. JOURNAL OF GRAPH THEORY, 2022, 100 (01) : 101 - 126