A Construction for Clique-Free Pseudorandom Graphs

被引：0
作者：
Anurag Bishnoi
Ferdinand Ihringer
Valentina Pepe
机构：
[1] The University of Western Australia,Department of Mathematics and Statistics
[2] Ghent University,Department of Mathematics: Analysis, Logic and Discrete Mathematics
[3] Sapienza University of Rome,Department of Basic and Applied Sciences for Engineering
来源：
Combinatorica | 2020年 / 40卷
关键词：
05D10; 51E20; 05E30;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A construction of Alon and Krivelevich gives highly pseudorandom Kk-free graphs on n vertices with edge density equal to Θ(n−1=(k−2)). In this short note we improve their result by constructing an infinite family of highly pseudorandom Kk-free graphs with a higher edge density of Θ(n−1=(k−1)).
引用
收藏
页码：307 / 314
页数：7
相关论文
共 24 条
  • [1] Alon N(1997)Constructive Bounds for a Ramsey-Type Problem Graphs Combin. 13 217-225
  • [2] Krivelevich M(1990)Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points J. Combin. Theory Ser. A 54 164-200
  • [3] Bannai E(2010)The early evolution of the H-free process Invent. Math. 181 291-336
  • [4] Hao S(2017)A sequence of triangle-free pseudorandom graphs Comb. Prob. Comp. 26 195-200
  • [5] Song S-Y(2013)Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz Combinatorica 33 181-197
  • [6] Bohman T(1995)Interlacing eigenvalues and graphs Linear Algebra Appl. 226-228 593-616
  • [7] Keevash P(1975)Strongly regular graphs Disc. Math. 13 357-381
  • [8] Conlon D(2019)New Strongly Regular Graphs from Finite Geometries via Switching Linear Algebra Appl. 580 464-474
  • [9] Fox J(2004)Triangle factors in sparse pseudorandom graphs Combinatorica 24 304-426
  • [10] Lee C(1971)Harmoniques sphériques sur un corps fini C. R. Acad. Sci. Paris Sr. A-B 272 A1642-A1645
123