Opened Access Phase transitions in the Ramsey-Turán theory
Estadísticas
Icon
Exportar a
Autor: Balogh, József
Coordinador/Director: Díaz Báñez, José Miguel
Garijo Royo, Delia
Márquez Pérez, Alberto
Urrutia Galicia, Jorge
Fecha: 2013
Publicado en: XV Spanish Meeting on Computational Geometry (2013), p 127-130
Tipo de documento: Ponencia
Resumen: Let f(n) be a function and L be a graph. Denote by RT(n, L, f(n)) the maximum number of edges of an L-free graph on n vertices with independence number less than f(n). Erdos and Sós asked if RT (n, K5, c√ n) = o (n2) for some constant c. We answer this question by proving the stronger RT(n, K5, o (√n log n)) = o(n2). It is known that RT (n, K5, c√n log n )= n2/4 + o (n2) for c > 1, so one can say that K5 has a Ramsey-Turán-phase transition at c√n log n. We extend this result to several other Kp's and functions f(n), determining many more phase transitions. We shall formulate several open problems, in particular, whether variants of the Bollobás-Erdos graph, which is a geometric construction, exist to give good lower bounds on RT (n, Kp, f(n)) for various pairs of p and f(n). These problems are studied in depth by Balogh-HuSimonovits, where among others, the Szemerédi's Regularity Lemma and the Hypergraph Dependent Random Choice Lemma are used.
Tamaño: 679.0Kb
Formato: PDF

URI: http://hdl.handle.net/11441/61088

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones