A sequence of triangle-free pseudorandom graphs

DOI10.1017/S0963548316000298MaRDI QIDQ5366941zbMATH OpenFDO

Authors David Conlon

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03773

zbMATH Keywords

highly pseudorandom triangle-free graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial aspects of finite geometries (05B25)

Abstract: A construction of Alon yields a sequence of highly pseudorandom triangle-free graphs with edge density significantly higher than one might expect from comparison with random graphs. We give an alternative construction for such graphs.

Recommendations

• A construction for clique-free pseudorandom graphs
• Embedding graphs with bounded degree in sparse pseudorandom graphs
• A clique-free pseudorandom subgraph of the pseudo polarity graph
• No dense subgraphs appear in the triangle-free graph process
• Triangle‐factors in pseudorandom graphs

Cites work

• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• Approximating the independence number via the -function
• Cutting a graph into two dissimilar halves
• Explicit Ramsey graphs and orthonormal labelings
• Extremal results in sparse pseudorandom graphs
• Hanson-Wright inequality and sub-Gaussian concentration
• Imbalances in k‐colorations
• Polarities and \(2k\)-cycle-free graphs
• Pseudo-random graphs
• The triangle-free process

Cited in

(10)

• A clique-free pseudorandom subgraph of the pseudo polarity graph
• Triangle‐factors in pseudorandom graphs
• A construction for clique-free pseudorandom graphs
• The asymptotics of \(r(4,t)\)
• Random cyclic triangle-free graphs of prime order
• On the extremal number of subdivisions
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Lovász, vectors, graphs and codes
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A note on pseudorandom Ramsey graphs

This page was built for publication: A sequence of triangle-free pseudorandom graphs

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