Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T06:39:55.234Z Has data issue: false hasContentIssue false
  • English
  • Français

A Sequence of Triangle-Free Pseudorandom Graphs

Published online by Cambridge University Press:  13 September 2016

DAVID CONLON
DAVID CONLON*
Affiliation:
Mathematical Institute, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Primary 05C35Secondary 05B25
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 195 - 200
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N. (1994) Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. 1 R12.Google Scholar
[2] Alon, N. and Kahale, N. (1998) Approximating the independence number via the θ-function. Math. Program. 80 253–264.Google Scholar
[3] Bohman, T. (2009) The triangle-free process. Adv. Math. 221 1653–1677.Google Scholar
[4] Conlon, D., Fox, J. and Zhao, Y. (2014) Extremal results in sparse pseudorandom graphs. Adv. Math. 256 206–290.Google Scholar
[5] Erdős, P., Goldberg, M., Pach, J. and Spencer, J. (1988) Cutting a graph into two dissimilar halves. J. Graph Theory 12 121–131.CrossRefGoogle Scholar
[6] Erdős, P. and Spencer, J. (1971/72) Imbalances in k-colorations. Networks 1 379–385.Google Scholar
[7] Hanson, D. L. and Wright, F. T. (1971) A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist. 42 1079–1083.CrossRefGoogle Scholar
[8] Krivelevich, M. and Sudakov, B. (2006) Pseudo-random graphs. In More Sets, Graphs and Numbers, Vol. 15 of Bolyai Society Mathematical Studies, Springer, pp. 199–262.Google Scholar
[9] Lazebnik, F., Ustimenko, V. A. and Woldar, A. J. (1999) Polarities and 2k-cycle-free graphs. Discrete Math. 197/198 503–513.Google Scholar
[10] Rudelson, M. and Vershynin, R. (2013) Hanson–Wright inequality and sub-Gaussian concentration. Electron. Commun. Probab. 18 1–9.Google Scholar