The number of the maximal triangle-free graphs
- Autores: József Balogh, Sárka Petrícková
- Localización: Bulletin of the London Mathematical Society, ISSN 0024-6093, Vol. 46, Nº 5, 2014, págs. 1003-1006
- Idioma: inglés
- DOI: 10.1112/blms/bdu059
- Enlaces
-
Resumen
Paul Erdos suggested the following problem: Determine or estimate the number of maximal triangle-free graphs on n vertices. Here we show that the number of maximal triangle-free graphs is at most 2 n 2 /8+o(n 2 ) , which matches the previously known lower bound.
Our proof uses among others the Ruzsa�Szemerédi triangle-removal lemma, and recent results on characterizing of the structure of independent sets in hypergraphs
¿Es nuevo? Regístrese
Ventajas de registrarse
