Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-06T02:52:40.427Z 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: david.conlon@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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

Information

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

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