of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:330369 |
| Date | January 2013 |
| Creators | Hladký, Jan |
| Contributors | Kráľ, Daniel, Keevash, Peter, Krivelevich, Michael |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0017 seconds