Auswahl der wissenschaftlichen Literatur zum Thema „Hypergraph regularity lemma“

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices isj-independentif its intersection with any edge has size strictly less thanj. The Kruskal–Katona theorem implies that in anr-uniform hypergraph with a fixed size and order, the hypergraph with the mostr-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number ofj-independent sets in anr-uniform hypergraph.

LetC(3)ndenote the 3-uniformtight cycle, that is, the hypergraph with verticesv1, .–.–.,vnand edgesv1v2v3,v2v3v4, .–.–.,vn−1vnv1,vnv1v2. We prove that the smallest integerN=N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph withNvertices contains a monochromatic copy ofC(3)nis asymptotically equal to 4n/3 ifnis divisible by 3, and 2notherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

Let Δ = Δ 1 × … × Δ d ⊆ R n \Delta =\Delta _1\times \ldots \times \Delta _d\subseteq \mathbb {R}^n , where R n = R n 1 × ⋯ × R n d \mathbb {R}^n=\mathbb {R}^{n_1}\times \cdots \times \mathbb {R}^{n_d} with each Δ i ⊆ R n i \Delta _i\subseteq \mathbb {R}^{n_i} a non-degenerate simplex of n i n_i points. We prove that any set S ⊆ R n S\subseteq \mathbb {R}^n , with n = n 1 + ⋯ + n d n=n_1+\cdots +n_d of positive upper Banach density necessarily contains an isometric copy of all sufficiently large dilates of the configuration Δ \Delta . In particular any such set S ⊆ R 2 d S\subseteq \mathbb {R}^{2d} contains a d d -dimensional cube of side length λ \lambda , for all λ ≥ λ 0 ( S ) \lambda \geq \lambda _0(S) . We also prove analogous results with the underlying space being the integer lattice. The proof is based on a weak hypergraph regularity lemma and an associated counting lemma developed in the context of Euclidean spaces and the integer lattice.

We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a densek-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

We continue the study of regular partitions of hypergraphs. In particular, we obtain corresponding counting lemmas for the regularity lemmas for hypergraphs from our paper ‘Regular Partitions of Hypergraphs: Regularity Lemmas’ (in this issue).

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.<br>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.

In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them. A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star. We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed. We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.

Étant donné un k-graph (hypergraphe k-uniforme) F, la densité de Turán π(F) de F est la densité maximale parmi tous les k-graphes F-libres. Déterminer π(F) pour un k-graph donné F est un problème extrémal classique. Étant donnés deux k-graphes F et H, un F-facteur de H est une collection de copies de F disjointes sur les sommets de H qui couvrent ensemble tous les sommets de H. Les problèmes de F-facteurs, en tant que renforcement du problème de Turán, visent à trouver des conditions extrémales sur H garantissant un F-facteur, ce qui a également une histoire longue et profonde. Dans cette thèse, nous utilisons de nombreux outils puissants, dont la méthode probabiliste, la méthode de régularité des hypergraphes et la méthode d'absorption, pour étudier les densités de Turán et les F-facteurs de k-graphes F donnés dans des hypergraphes uniformément denses. Contrairement aux graphes, nous savons tous qu'il existe plusieurs notions non équivalentes de quasi-aléatoire dans les k-graphes pour k ≥ 3. Par conséquent, notre travail propose également plusieurs définitions non équivalentes de k-graphes uniformément denses. En gros, un k-graphe H est (d, μ, ⋆)-dense signifie qu'il est d-dense et ⋆-quasi-aléatoire pour une petite valeur de μ &gt; 0 par rapport à des structures aléatoires données. En se limitant aux 3-graphes (d, μ, 1)-dense, la densité de Turán d'un 3-graphe donné F est notée π1(F). La détermination de π1(F) a été suggérée par Erdős et Sós dans les années 1980. En 2018, Reiher, Rödl et Schacht ont étendu le concept de 3-graphes (d, μ, 1)-dense à des k-graphes (d, μ, k-2)-dense pour k ≥ 3, et ils ont proposé l'étude de la densité de Turán uniforme πk-2(F) pour un k-graphe donné F dans des k-graphes (d, μ, k-2)-dense. En particulier, ils ont montré que πk-2(•) saute de 0 à au moins k-à-la-moins-k-ème puissance. Dans cette thèse, nous obtenons une condition suffisante pour les 3-graphes F qui satisfont π1(F) = 1/4. De manière intéressante, actuellement, tous les 3-graphes F connus dont π1(F) est de 1/4 satisfont cette condition. De plus, nous construisons également quelques 3-graphes intrigants F avec π1(F) = 1/4. Pour les k-graphes, nous donnons un cadre pour étudier πk-2(F) pour n'importe quel k-graphe F. En utilisant ce cadre, nous donnons une condition suffisante pour les k-graphes F satisfaisant πk-2(F) est k-à-la-moins-k-ème puissance, et nous construisons une famille infinie de k-graphes avec πk-2(F) est k-à-la-moins-k-ème puissance. En 2016, Lenz et Mubayi ont posé le problème de caractériser les k-graphes F tels que chaque k-graphe H suffisamment grand (d, μ, dot)-dense avec d &gt; 0, v(F)|v(H) et un degré minimum de sommet positif contient un F-facteur. Motivés par ce problème, nous démontrons un théorème général sur les F-facteurs qui réduit le problème des F-facteurs de Lenz et Mubayi à un sous-problème naturel, c'est-à-dire le problème de F-cover. En utilisant ce résultat, nous répondons à la question de Lenz et Mubayi pour ceux F qui sont des k-graphes k-partis et pour tous les 3-graphes F, séparément. Dans le travail de Lenz et Mubayi, ils ont également construit une séquence de 3-graphes (1/8, μ, dot)-dense avec un degré minimum de sommet positif n'ayant pas de F-facteur, où F est un 3-graph k-parti complet équilibré. Dans cette thèse, nous prouvons que 1/8 est le seuil de densité pour garantir tous les 3-graphes 3-partis facteurs dans (d, μ, dot)-dense 3-graphes avec une condition de minimum degré de sommet Ω(n). De plus, nous montrons que l'on ne peut pas remplacer la condition de minimum degré de sommet par une condition de minimum degré de sommet. En particulier, nous étudions le seuil de densité optimal des F-facteurs pour chaque 3-graph 3-parti F dans (d, μ, dot)-dense 3-graphes avec un minimum degré de sommet Ω(n). De plus, nous étudions également les problèmes de F-facteurs pour les k-graphes k-partis F avec une hypothèse quasi-aléatoire plus forte et un minimum degré de sommet positif<br>Given a k-graph (k-uniform hypergraph) F, the Turán density π(F) of F is the maximum density among all F-free k-graphs. Determining π(F) for a given k-graph F is a classical extremal problem. Given two k-graphs F and H, a perfect F-tiling (or F-factor) of H is a collection of vertex-disjoint copies of F in H that together cover all the vertices of H. Perfect tiling problems, as a strengthening of the Turán problem, aim to find extremal conditions on H which guarantee an F-factor, which also has a long and profound history. In this thesis, we use many powerful tools including the probabilistic method, hypergraph regularity method and absorbing method to study Turán densities and perfect tilings of given k-graphs F in uniformly dense hypergraphs. Unlike graphs, we all know that there are several non-equivalent notions of quai-randomness in k-graphs for k ≥ 3. Hence, our work also has several non-equivalent definitions of uniformly dense k-graphs. Roughly speaking, a k-graph H is (d, μ, ⋆)-dense means that it is d-dense and ⋆-quai-randomness for some small μ &gt; 0 with respect to given random structures. Restricting to (d, μ, 1)-dense 3-graphs, the Turán density of a given 3-graph F is denoted by π1(F). Determining π1(F) was suggested by Erdős and Sós in the 1980s. In 2018, Reiher, Rödl and Schacht extended the concept of (d, μ, 1)-dense 3-graphs to (d, μ, k-2)-dense k-graphs for k ≥ 3, and they proposed the study of uniform Turán density πk-2(F) for a given k-graph F in (d, μ, k-2)-dense k-graphs. In particular, they showed that πk-2(•) “jumps” from 0 to at least k-to-the-minus-kth-power. In this thesis, we obtain a sufficient condition for 3-graphs F which satisfy π1(F)= 1/4. Interestingly, currently all known 3-graphs F whose π1(F) is 1/4 satisfy this condition. In addition, we also construct some intriguing 3-graphs F with π1(F) = 1/4. For k-graphs, we give a framework to study πk-2(F) for any k-graph F. By using this framework, we give a sufficient condition for k-graphs F satisfying πk-2(F) is k-to-the-minus-kth-power, and construct an infinite family of k-graphs with πk-2(F) is k-to-the-minus-kth-power.In 2016, Lenz and Mubayi posed the problem of characterizing the k-graphs F such that every sufficiently large (d, μ, dot)-dense k-graph H with d &gt; 0, v(F)|v(H) and positive minimum vertex degree contains an F-factor. Motivated by this problem, we prove a general theorem on F-factors which reduces the F-factors problem of Lenz and Mubayi to a natural sub-problem, that is, the F-cover problem. By using this result, we answer the question of Lenz and Mubayi for those F which are k-partite k-graphs and for all 3-graphs F, separately. In the work of Lenz and Mubayi, they also constructed a sequence of (1/8, μ, dot)-dense 3-graphs with positive minimum vertex degree having no F-factor, where F is a balanced complete 3-partite 3-graph. In this thesis, we prove that 1/8 is the density threshold for ensuring all 3-partite 3-graphs perfect tilings in (d, μ, dot)-dense 3-graphs given a minimum codegree condition Ω(n). Moreover, we show that one can not replace the minimum codegree condition with a minimum vertex degree condition. In particular, we study the optimal density threshold of F-factors for each 3-partite 3-graph F in (d, μ, dot)-dense 3-graphs with minimum codegree Ω(n). In addition, we also study F-factor problems for k-partite k-graphs F with stronger quasi-random assumption and positive minimum 1-degree

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.<br>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.

In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln angegeben. Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergraphen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten, studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche Klasse von Hypergraphen bewiesen. Es wird für viele Hypergraphen F, deren extremaler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen.<br>This thesis presents first one possible generalization of the result of Chung, Graham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-randomness. As applications we obtain a simple strong refutation algorithm for random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for quasi-random graphs. Our focus then shifts from the study of quasi-random objects to applications of different versions of the hypergraph regularity lemmas; all these versions assert decompositions of hypergraphs into constantly many quasi-random parts, where the meaning of ``quasi-random'''' takes different contexts in different situations. We study the family of hypergraphs not containing the hypergraph of the Fano plane as a subhypergraph, and show that almost all members of this family are bipartite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs with average polynomial running time is given. Then the following combinatorial extremal problem is considered. Suppose one is given r colors and a fixed hypergraph F. The question is: In at most how many ways can one color the hyperedges of a hypergraph H on n vertices such that no monochromatic copy of F is created? What are the extremal hypergraphs for this function? Here a structural result for a natural family of hypergraphs F is proven. For some special classes of hypergraphs we show that their extremal hypergraphs (for large n) maximize the number of edge colorings for 2 and 3 colors, while for at least 4 colors other hypergraphs are optimal.