Academic literature on the topic 'Quasi-random hypergraph'

In 1964, Erdős proved that for any $\alpha > 0$, an $l$-uniform hypergraph $G$ with $n \geq n_0(\alpha, l)$ vertices and $\alpha \binom{n}{l}$ edges contains a large complete $l$-equipartite subgraph. This implies that any sufficiently large $G$ with density $\alpha > 0$ contains a large subgraph with density at least $l!/l^l$.In this note we study a similar problem for $l$-uniform hypergraphs $Q$ with a weak quasi-random property (i.e. with edges uniformly distributed over the sufficiently large subsets of vertices). We prove that any sufficiently large quasi-random $l$-uniform hypergraph $Q$ with density $\alpha > 0$ contains a large subgraph with density at least $\frac{(l-1)!}{l^{l-1}-1}$. In particular, for $l=3$, any sufficiently large such $Q$ contains a large subgraph with density at least $\frac{1}{4}$ which is the best possible lower bound.We define jumps for quasi-random sequences of $l$-graphs and our result implies that every number between 0 and $\frac{(l-1)!}{l^{l-1}-1}$ is a jump for quasi-random $l$-graphs. For $l=3$ this interval can be improved based on a recent result of Glebov, Král' and Volec. We prove that every number between [0, 0.3192) is a jump for quasi-random $3$-graphs.

É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 μ > 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 > 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
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 μ > 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 > 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

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