A construction for clique-free pseudorandom graphs

DOI10.1007/S00493-020-4226-6MaRDI QIDQ2216919zbMATH OpenOpenAlexFDO

Authors Anurag Bishnoi, Ferdinand Ihringer, Valentina Pepe

Publication date 18 December 2020

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.04677, https://biblio.ugent.be/publication/8662761

zbMATH Keywords

edge densitypseudorandom graphsRamsey numbers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10) Association schemes, strongly regular graphs (05E30) Combinatorial structures in finite projective spaces (51E20)

Abstract: A construction of Alon and Krivelevich gives highly pseudorandom $K_k$-free graphs on $n$ vertices with edge density equal to $Theta(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 $Theta(n^{-1/(k-1)})$.

Recommendations

• A clique-free pseudorandom subgraph of the pseudo polarity graph
• A sequence of triangle-free pseudorandom graphs
• scientific article; zbMATH DE number 2196516
• Clique-factors in sparse pseudorandom graphs
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs

Cites work

• A generalization of Turán's theorem
• A sequence of triangle-free pseudorandom graphs
• Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Constructive bounds for a Ramsey-type problem
• Explicit Ramsey graphs and orthonormal labelings
• Finite geometry and combinatorial applications
• scientific article; zbMATH DE number 3884175 (Why is no real title available?)
• scientific article; zbMATH DE number 4034346 (Why is no real title available?)
• scientific article; zbMATH DE number 812124 (Why is no real title available?)
• scientific article; zbMATH DE number 3344757 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• New strongly regular graphs from finite geometries via switching
• Pseudo-random graphs
• Strongly regular graphs
• The early evolution of the \(H\)-free process
• Triangle factors in sparse pseudo-random graphs

Cited in

(12)

• Graphs associated with orthogonal collections of k-planes over finite fields
• Regular Turán numbers of complete bipartite graphs
• Approximately strongly regular graphs
• A clique-free pseudorandom subgraph of the pseudo polarity graph
• Multicolor Ramsey numbers via pseudorandom graphs
• Recognizing sets of generators in finite polar spaces
• A sequence of triangle-free pseudorandom graphs
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• A note on pseudorandom Ramsey graphs
• Turán problems in pseudorandom graphs
• Association schemes and orthogonality graphs on anisotropic points of polar spaces
• Clique factors in pseudorandom graphs

This page was built for publication: A construction for clique-free pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216919)