Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-11T02:40:27.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Universality of Graphs with Few Triangles and Anti-Triangles

Part of: Graph theory

Published online by Cambridge University Press:  29 July 2015

DAN HEFETZ  and
MYKHAYLO TYOMKYN
DAN HEFETZ
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK (e-mail: d.hefetz@bham.ac.uk, m.tyomkyn@bham.ac.uk)
MYKHAYLO TYOMKYN
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK (e-mail: d.hefetz@bham.ac.uk, m.tyomkyn@bham.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.

We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-triangles converge to 1/8. Since the random graph $\mathcal{G}$ n,1/2 is, in particular, 3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern [10]. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ⩾ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every ℓ there are 3-random-like graphs which are ℓ-universal but not m-universal when m is sufficiently large compared to ℓ.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 4 , July 2016 , pp. 560 - 576
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.Google Scholar
[2] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley.Google Scholar
[3] Balister, P. Personal communication.Google Scholar
[4] Bollobás, B. (1998) Modern Graph Theory, corrected edition, Graduate texts in Mathematics, Springer.CrossRefGoogle Scholar
[5] Chung, F. R. K., Graham, R. L. and Wilson, R. M. (1989) Quasi-random graphs. Combinatorica 9 345–362.Google Scholar
[6] Erdős, P. (1962) On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kulató Int. Kőzl 7 459–464.Google Scholar
[7] Erdős, P. and Hajnal, A. (1989) Ramsey-type theorems. Discrete Appl. Math. 25 37–52.CrossRefGoogle Scholar
[8] Falgas-Ravry, V. and Vaughan, E. R. (2013) Applications of the semi-definite method to the Turán density problem for 3-graphs. Combin. Probab. Comput. 22 21–54.CrossRefGoogle Scholar
[9] Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.Google Scholar
[10] Linial, N. and Morgenstern, A. Graphs with few 3-cliques and 3-anticliques are 3-universal. J. Graph Theory, to appear. arXiv.org:1306.2020 Google Scholar
[11] Radziszowski, S. (2011) Small Ramsey numbers. Electron. J. Combin. DS1.CrossRefGoogle Scholar
[12] Seinsche, D. (1974) On a property of the class of n-colorable graphs. J. Combin. Theory Ser. B 16 191–193.Google Scholar
[13] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Proc. Colloq., Tihany, 1966, Academic, pp. 279–319.Google Scholar
[14] Thomason, A. (1987) Pseudorandom graphs. In Random Graphs'85: Poznań, 1985, Vol. 144 of North-Holland Mathematics Studies, North-Holland, pp. 307–331.Google Scholar
[15] Thomason, A. (1989) A disproof of a conjecture of Erdős in Ramsey theory. J. London Math. Soc 39 246–255.Google Scholar