Advanced search
2 files | 621.16 KB Add to list

A construction for clique-free pseudorandom graphs

(2020) COMBINATORICA. 40(3). p.307-314
Author
Organization
Abstract
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)).
Keywords
Discrete Mathematics and Combinatorics, Computational Mathematics

Downloads

  • Bishnoi-Ihringer-Pepe19 revised v03.pdf
    • full text (Accepted manuscript)
    • |
    • open access
    • |
    • PDF
    • |
    • 259.19 KB
  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 361.97 KB

Citation

Please use this url to cite or link to this publication:

MLA
Bishnoi, Anurag, et al. “A Construction for Clique-Free Pseudorandom Graphs.” COMBINATORICA, vol. 40, no. 3, 2020, pp. 307–14, doi:10.1007/s00493-020-4226-6.
APA
Bishnoi, A., Ihringer, F., & Pepe, V. (2020). A construction for clique-free pseudorandom graphs. COMBINATORICA, 40(3), 307–314. https://doi.org/10.1007/s00493-020-4226-6
Chicago author-date
Bishnoi, Anurag, Ferdinand Ihringer, and Valentina Pepe. 2020. “A Construction for Clique-Free Pseudorandom Graphs.” COMBINATORICA 40 (3): 307–14. https://doi.org/10.1007/s00493-020-4226-6.
Chicago author-date (all authors)
Bishnoi, Anurag, Ferdinand Ihringer, and Valentina Pepe. 2020. “A Construction for Clique-Free Pseudorandom Graphs.” COMBINATORICA 40 (3): 307–314. doi:10.1007/s00493-020-4226-6.
Vancouver
1.
Bishnoi A, Ihringer F, Pepe V. A construction for clique-free pseudorandom graphs. COMBINATORICA. 2020;40(3):307–14.
IEEE
[1]
A. Bishnoi, F. Ihringer, and V. Pepe, “A construction for clique-free pseudorandom graphs,” COMBINATORICA, vol. 40, no. 3, pp. 307–314, 2020.
@article{8662761,
  abstract     = {{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)).}},
  author       = {{Bishnoi, Anurag and Ihringer, Ferdinand and Pepe, Valentina}},
  issn         = {{0209-9683}},
  journal      = {{COMBINATORICA}},
  keywords     = {{Discrete Mathematics and Combinatorics,Computational Mathematics}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{307--314}},
  title        = {{A construction for clique-free pseudorandom graphs}},
  url          = {{http://dx.doi.org/10.1007/s00493-020-4226-6}},
  volume       = {{40}},
  year         = {{2020}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: