A sequence of triangle-free pseudorandom graphs
From MaRDI portal
Publication:5366941
DOI10.1017/S0963548316000298zbMATH Open1371.05259arXiv1602.03773MaRDI QIDQ5366941FDOQ5366941
Authors: David Conlon 
Publication date: 10 October 2017
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1602.03773
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial aspects of finite geometries (05B25)
Cites Work
- Hanson-Wright inequality and sub-Gaussian concentration
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
- The triangle-free process
- Extremal results in sparse pseudorandom graphs
- Polarities and \(2k\)-cycle-free graphs
- Cutting a graph into two dissimilar halves
- Pseudo-random graphs
- Approximating the independence number via the \(\vartheta\)-function
- Explicit Ramsey graphs and orthonormal labelings
- Imbalances in k‐colorations
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)
