dc.contributor.editor | Díaz Báñez, José Miguel | es |
dc.contributor.editor | Garijo Royo, Delia | es |
dc.contributor.editor | Márquez Pérez, Alberto | es |
dc.contributor.editor | Urrutia Galicia, Jorge | es |
dc.creator | Balogh, József | es |
dc.date.accessioned | 2017-06-07T11:24:04Z | |
dc.date.available | 2017-06-07T11:24:04Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | Balogh, J. (2013). Phase transitions in the Ramsey-Turán theory. En XV Spanish Meeting on Computational Geometry, Sevilla. | |
dc.identifier.uri | http://hdl.handle.net/11441/61088 | |
dc.description.abstract | 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. | es |
dc.description.sponsorship | National Science Foundation | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | XV Spanish Meeting on Computational Geometry (2013), pp. 119-122. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Phase transitions in the Ramsey-Turán theory | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada II | |
dc.relation.projectID | DMS-0745185 | es |
dc.relation.publisherversion | http://congreso.us.es/ecgeometry/proceedingsECG2013.pdf | es |
idus.format.extent | 4 p. | es |
dc.publication.initialPage | 119 | es |
dc.publication.endPage | 122 | es |
dc.eventtitle | XV Spanish Meeting on Computational Geometry | es |
dc.eventinstitution | Sevilla | es |