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

Randomness is an invaluable resource in theoretical computer science. However, pure random bits are hard to obtain. Quasi-randomness is a tool that has been widely used in eliminating/reducing the randomness from randomized algorithms. In this thesis, we study some aspects of quasi-randomness in graphs. Specifically, we provide an algorithm and a lower bound for two different kinds of regularity lemmas. Our algorithm for FK-regularity is derived using a spectral characterization of quasi-randomness. We also use a similar spectral connection to also answer an open question about quasi-random tournaments. We then provide a "Wowzer" type lower bound (for the number of parts required) for the strong regularity lemma. Finally, we study the derandomization of complexity classes using Turing machine simulations. 1. Connections between quasi-randomness and graph spectra. Quasi-random (or pseudo-random) objects are deterministic objects that behave almost like truly random objects. These objects have been widely studied in various settings (graphs, hypergraphs, directed graphs, set systems, etc.). In many cases, quasi-randomness is very closely related to the spectral properties of the combinatorial object that is under study. In this thesis, we discover the spectral characterizations of quasi-randomness in two different cases to solve open problems. A Deterministic Algorithm for Frieze-Kannan Regularity: The Frieze-Kannan regularity lemma asserts that any given graph of large enough size can be partitioned into a number of parts such that, across parts, the graph is quasi-random. . It was unknown if there was a deterministic algorithm that could produce a parition satisfying the conditions of the Frieze-Kannan regularity lemma in deterministic sub-cubic time. In this thesis, we answer this question by designing an O(n[superscript]w) time algorithm for constructing such a partition, where w is the exponent of fast matrix multiplication. Even Cycles and Quasi-Random Tournaments: Chung and Graham in had provided several equivalent characterizations of quasi-randomness in tournaments. One of them is about the number of "even" cycles where even is defined in the following sense. A cycle is said to be even, if when walking along it, an even number of edges point in the wrong direction. Chung and Graham showed that if close to half of the 4-cycles in a tournament T are even, then T is quasi-random. They asked if the same statement is true if instead of 4-cycles, we consider k-cycles, for an even integer k. We resolve this open question by showing that for every fixed even integer k geq 4, if close to half of the k-cycles in a tournament T are even, then T must be quasi-random. 2. A Wowzer type lower bound for the strong regularity lemma. The regularity lemma of Szemeredi asserts that one can partition every graph into a bounded number of quasi-random bipartite graphs. Alon, Fischer, Krivelevich and Szegedy obtained a variant of the regularity lemma that allows one to have an arbitrary control on this measure of quasi-randomness. However, their proof only guaranteed to produce a partition where the number of parts is given by the Wowzer function, which is the iterated version of the Tower function. We show here that a bound of this type is unavoidable by constructing a graph H, with the property that even if one wants a very mild control on the quasi-randomness of a regular partition, then any such partition of H must have a number of parts given by a Wowzer-type function. 3. How fast can we deterministically simulate nondeterminism? We study an approach towards derandomizing complexity classes using Turing machine simulations. We look at the problem of deterministically counting the exact number of accepting computation paths of a given nondeterministic Turing machine. We provide a deterministic algorithm, which runs in time roughly O(sqrt(S)), where S is the size of the configuration graph. The best of the previously known methods required time linear in S. Our result implies a simulation of probabilistic time classes like PP, BPP and BQP in the same running time. This is an improvement over the currently best known simulation by van Melkebeek and Santhanam.

Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.

Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.

Einst als Hilfssatz für Szemerédis Theorem entwickelt, hat sich das Regularitätslemma in den vergangenen drei Jahrzehnten als eines der wichtigsten Werkzeuge der Graphentheorie etabliert. Im Wesentlichen hat das Lemma zum Inhalt, dass dichte Graphen durch eine konstante Anzahl quasizufälliger, bipartiter Graphen approximiert werden können, wodurch zwischen deterministischen und zufälligen Graphen eine Brücke geschlagen wird. Da letztere viel einfacher zu handhaben sind, stellt diese Verbindung oftmals eine wertvolle Zusatzinformation dar. Vom Regularitätslemma ausgehend gliedert sich die vorliegende Arbeit in zwei Teile. Mit Fragestellungen der Extremalen Hypergraphentheorie beschäftigt sich der erste Teil der Arbeit. Es wird zunächst eine Version des Regularitätslemmas Hypergraphen angewandt, um asymptotisch scharfe Schranken für das Auftreten von Hamiltonkreisen in uniformen Hypergraphen mit hohem Minimalgrad herzuleiten. Nachgewiesen werden des Weiteren asymptotisch scharfe Schranken für die Existenz von perfekten und nahezu perfekten Matchings in uniformen Hypergraphen mit hohem Minimalgrad. Im zweiten Teil der Arbeit wird ein neuer, Szemerédis ursprüngliches Konzept generalisierender Regularitätsbegriff eingeführt. Diesbezüglich wird ein Algorithmus vorgestellt, welcher zu einem gegebenen Graphen ohne zu dichte induzierte Subgraphen eine reguläre Partition in polynomieller Zeit berechnet. Als eine Anwendung dieses Resultats wird gezeigt, dass das Problem MAX-CUT für die oben genannte Graphenklasse in polynomieller Zeit bis auf einen multiplikativen Faktor von (1+o(1)) approximierbar ist. Der Untersuchung von Chung, Graham und Wilson zu quasizufälligen Graphen folgend wird ferner der sich aus dem neuen Regularitätskonzept ergebende Begriff der Quasizufälligkeit studiert und in Hinsicht darauf eine Charakterisierung mittels Eigenwertseparation der normalisierten Laplaceschen Matrix angegeben. / Once invented as an auxiliary lemma for Szemerédi''s Theorem the regularity lemma has become one of the most powerful tools in graph theory in the last three decades which has been widely applied in several fields of mathematics and theoretical computer science. Roughly speaking the lemma asserts that dense graphs can be approximated by a constant number of bipartite quasi-random graphs, thus, it narrows the gap between deterministic and random graphs. Since the latter are much easier to handle this information is often very useful. With the regularity lemma as the starting point two roads diverge in this thesis aiming at applications of the concept of regularity on the one hand and clarification of several aspects of this concept on the other. In the first part we deal with questions from extremal hypergraph theory and foremost we will use a generalised version of Szemerédi''s regularity lemma for uniform hypergraphs to prove asymptotically sharp bounds on the minimum degree which ensure the existence of Hamilton cycles in uniform hypergraphs. Moreover, we derive (asymptotically sharp) bounds on minimum degrees of uniform hypergraphs which guarantee the appearance of perfect and nearly perfect matchings. In the second part a novel notion of regularity will be introduced which generalises Szemerédi''s original concept. Concerning this new concept we provide a polynomial time algorithm which computes a regular partition for given graphs without too dense induced subgraphs. As an application we show that for the above mentioned class of graphs the problem MAX-CUT can be approximated within a multiplicative factor of (1+o(1)) in polynomial time. Furthermore, pursuing the line of research of Chung, Graham and Wilson on quasi-random graphs we study the notion of quasi-randomness resulting from the new notion of regularity and concerning this we provide a characterisation in terms of eigenvalue separation of the normalised Laplacian matrix.

Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet. / About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.

[pt] Consideramos, nesta dissertação, a questão de determinar se um grafo tem uma propriedade P, tal como G é livre de triângulos ou G é 4- colorível. Em particular, consideramos para quais propriedades P existe um algoritmo aleatório com probabilidades de erro constantes que aceita grafos que satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça. Se, além disso, o algoritmo tiver complexidade independente do tamanho do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon, Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de propriedades testáveis de grafos, resolvendo um problema em aberto levantado em 1996. Essa caracterização diz informalmente que uma propriedade P de um grafo é testável se e somente se testar P pode ser reduzido a testar a propriedade de satisfazer uma das finitas partições Szemerédi. / [en] We consider, in this thesis, the question of determining if a graph has a property P such as G is triangle-free or G is 4-colorable. In particular, we consider for which properties P there exists a random algorithm with constant error probabilities that accept graphs that satisfy P and reject graphs that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm has complexity independent of the size of the graph, the property is called testable. We will discuss the results of Alon, Fischer, Newman, and Shapira that obtained a combinatorial characterization of testable graph properties, solving an open problem raised in 1996. This characterization informally says that a graph property P is testable if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions.