A construction for clique-free pseudorandom graphs

2019/05/12 by Bishnoi, Anurag, Ihringer, Ferdinand, Pepe, Valentina · 2 citations
#05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1905.04677

Abstract

A construction of Alon and Krivelevich gives highly pseudorandom K_k-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 K_k-free graphs with a higher edge density of Θ(n^{-1/(k - 1)}).

Cited by

• Incidence theorems for multivariate polynomials over finite fields
• Combinatorial theorems relative to sparse sets

Related

• A clique-free pseudorandom subgraph of the pseudo polarity graph
• Spectrally indistinguishable pseudorandom graphs
• On the structure of dense graphs with fixed clique number
• Near-perfect clique-factors in sparse pseudorandom graphs
• Clique factors in pseudorandom graphs