Academic literature on the topic 'Extremal hypergraph theory'

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.

The distance spectral radius of a connected hypergraph is the largest eigenvalue of its distance matrix. The unique hypertrees with minimum distance spectral radii are determined in the class of hypertrees of given diameter, in the class of hypertrees of given matching number, and in the class of non-hyperstar-like hypertrees, respectively. The unique hypergraphs with minimum and second minimum distance spectral radii are determined in the class of unicylic hypergraphs. The unique hypertree with maximum distance spectral radius is determined in the class of $k$-th power hypertrees of given matching number.

The classical graph entropy based on the vertex coloring proposed by Mowshowitz depends on a graph. In fact, a hypergraph, as a generalization of a graph, can express complex and high-order relations such that it is often used to model complex systems. Being different from the classical graph entropy, we extend this concept to a hypergraph. Then, we define the graph entropy based on the vertex strong coloring of a hypergraph. Moreover, some tightly upper and lower bounds of such graph entropies as well as the corresponding extremal hypergraphs are obtained.

Lots of symmetric properties are well-explored and analyzed in extremal graph theory, such as the well-known symmetrization operation in the Turán problem and the high symmetric in the extremal graphs. This paper is devoted to studying the Lagrangian of hypergraphs, which connects to a very symmetric function—the Lagrangian function. Given an r-uniform hypergraph F, the Lagrangian density πλ(F) is the limit supremum of r!λ(G) over all F-free G, where λ(G) is the Lagrangian of G. An r-uniform hypergraph F is called λ-perfect if πλ(F) equals r!λ(Kv(F)−1r). Yan and Peng conjectured that: for integer r≥3, there exists n0(r) such that if G and H are two λ-perfect r-graphs with |V(G)| and |V(H)| no less than n0(r), then the disjoint union of G and H is λ-perfect. Let St denote a 3-uniform hypergraph with t edges {e1,⋯,et} satisfying that ei∩ej={v} for all 1≤i<j≤t. In this paper, we show that the conjecture holds for G=S2 and H=St for all t≥62. Moreover, our result yields a class of Turán densities of 3-uniform hypergraphs. In our proof, we use some new techniques to study Lagrangian density problems; using a result of Sidorenko to find subgraphs, and a result of Talbot to upper bound the Lagrangian of a hypergraph.

AbstractA well-known observation of Lovász is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lovász’s criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable n-uniform hypergraph. Our main result is an exact answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollobás’s two families theorem with Pluhar’s randomized colouring algorithm.

Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{F}$ comprising hypergraphs H with minimum degree at least $c \binom{| V(H) |}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r = 2), and in this paper we begin its systematic study for hypergraphs.Łuczak and Thomassé recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Turán number is achieved uniquely by the complete (r + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Turán number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle.In order to prove upper bounds we introduce the concept of fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre bundles that is based on the idea of Vapnik–Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemerédi for graphs and might be of independent interest. Many open problems remain.

The partition number of a product hypergraph is introduced as the minimal size of a partition of its vertex set into sets that are edges. This number is shown to be multiplicative if all factors are graphs with all loops included.

Abstract A central problem in extremal graph theory is to estimate, for a given graph H, the number of H-free graphs on a given set of n vertices. In the case when H is not bipartite, Erd̋s, Frankl, and Rödl proved that there are 2(1+o(1))ex(n, H) such graphs. In the bipartite case, however, bounds of the form 2O(ex(n, H)) have been proven only for relatively few special graphs H. As a 1st attempt at addressing this problem in full generality, we show that such a bound follows merely from a rather natural assumption on the growth rate of n ↦ ex(n, H); an analogous statement remains true when H is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd̋s and Simonovits. The bounds on the number of H-free hypergraphs are derived from it using the method of hypergraph containers.

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.

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.

For integers $n \geq k \geq 2$, let $V$ be an $n$-element set, and let $\binom{V}{k}$ denote the family of all $k$-element subsets of $V$. For disjoint subsets $A, B \subseteq V$, we say that $\{A, B\}$ {\it covers} an element $K \in \binom{V}{k}$ if $K \subseteq A \dot\cup B$ and $K \cap A \neq \emptyset \neq K \cap B$. We say that a collection $\cC$ of such pairs {\it covers} $\binom{V}{k}$ if every $K \in \binom{V}{k}$ is covered by at least one $\{A, B\} \in \cC$. When $k=2$, covers $\cC$ of $\binom{V}{2}$ were introduced in~1961 by R\'enyi~\cite{Renyi}, where they were called {\it separating systems} of $V$ (since every pair $u \neq v \in V$ is separated by some $\{A, B\} \in \cC$, in the sense that $u \in A$ and $v \in B$, or vice-versa). Separating systems have since been studied by many authors. For a cover $\cC$ of $\binom{V}{k}$, define the {\it weight} $\omega(\cC)$ of $\cC$ by $\omega(\cC) = \sum_{\{A, B\} \in \cC} (|A|+|B|)$. We define $h(n, k)$ to denote the minimum weight $\omega(\cC)$ among all covers $\cC$ of $\binom{V}{k}$. In~1964, Hansel~\cite{H} determined the bounds $\lceil n \log_2 n \rceil \leq h(n, 2) \leq n\lceil \log_2 n\rceil$, which are sharp precisely when $n = 2^p$ is an integer power of two. In~2007, Bollob\'as and Scott~\cite{BS} extended Hansel's bound to the exact formula $h(n, 2) = np + 2R$, where $n = 2^p + R$ for $p = \lfloor \log_2 n\rfloor$. The primary result of this dissertation extends the results of Hansel and of Bollob\'as and Scott to the following exact formula for $h(n, k)$, for all integers $n \geq k \geq 2$. Let $n = (k-1)q + r$ be given by division with remainder, and let $q = 2^p + R$ satisfy $p = \lfloor \log_2 q \rfloor$. Then h(n, k) = np + 2R(k-1) + \left\lceil\frac{r}{k-1}\right\rceil (r + k - 1). A corresponding result of this dissertation proves that all optimal covers $\cC$ of $\binom{V}{k}$, i.e., those for which $\omega(\cC) = h(n, k)$, share a unique {\it degree-sequence}, as follows. For a vertex $v \in V$, define the {\it $\cC$-degree} $\deg_{\cC}(v)$ of $v$ to be the number of elements $\{A, B\} \in \cC$ for which $v \in A \dot\cup B$. We order these degrees in non-increasing order to form $\bd(\cC)$, and prove that when $\cC$ is optimal, $\bd(\cC)$ is necessarily binary with digits $p$ and $p+1$, where uniquely the larger digits occur precisely on the first $2R(k-1) + \lceil r/(k-1) \rceil (r + k - 1)$ many coordinates. That $\bd(\cC)$ satisfies the above for optimal $\cC$ clearly implies the claimed formula for $h(n,k)$, but in the course of this dissertation, we show these two results are, in fact, equivalent. In this dissertation, we also consider a $d$-partite version of covers $\cC$, written here as {\it $d$-covers} $\cD$. Here, the elements $\{A,B\} \in \cC$ are replaced by $d$-element families $\{A_1, \dots, A_d\} \in \cD$ of pairwise disjoint sets $A_i \subset V$, $1 \leq i \leq d$. We require that every element $K \in \binom{V}{k}$ is covered by some $\{A_1, \dots, A_d\} \in \cD$, in the sense that $K \subseteq A_1 \dot\cup \cdots \dot\cup A_d$ where $K \cap A_i \neq \emptyset$ holds for each $1 \leq i \leq d$. We analogously define $h_d(n,k)$ as the minimum weight $\omega(\cD) = \sum_{D \in \cD} \sum_{A \in D} |A|$ among all $d$-covers $\cD$ of $\binom{V}{k}$. In this dissertation, we prove that for all $2 \leq d \leq k \leq n$, the bound $h_d(n,k) \geq n \log_{d/(d-1)} (n/(k-1))$ always holds, and that this bound is asymptotically sharp whenever $d = d(k) = O (k/\log^2 k)$ and $k = k(n) = O(\sqrt{\log \log n})$.

The results in this thesis concern extremal and probabilistic topics in number theoretic settings. We prove sufficient conditions on when certain types of integer solutions to linear systems of equations in binomial random sets are distributed normally, results on the typical approximate structure of pairs of integer subsets with a given sumset cardinality, as well as upper bounds on how large a family of integer sets defining pairwise distinct sumsets can be. In order to prove the typical structural result on pairs of integer sets, we also establish a new multipartite version of the method of hypergraph containers, generalizing earlier work by Morris, Saxton and Samotij.
L'objectiu de la combinatòria additiva “històricament també anomenada teoria combinatòria de nombres” és la d’estudiar l'estructura additiva de conjunts en determinats grups ambient. La combinatòria extremal estudia quant de gran pot ser una col·lecció d'objectes finits abans d'exhibir determinats requisits estructurals. La combinatòria probabilística analitza estructures combinatòries aleatòries, identificant en particular l'estructura dels objectes combinatoris típics. Entre els estudis més celebrats hi ha el treball de grafs aleatoris iniciat per Erdös i Rényi. Un exemple especialment rellevant de com aquestes tres àrees s'entrellacen és el desenvolupament per Erdös del mètode probabilístic en teoria de nombres i en combinatòria, que mostra l'existència de moltes estructures extremes en configuracions additives utilitzant tècniques probabilistes. Tots els temes d'aquesta tesi es troben en la intersecció d'aquestes tres àrees, i apareixen en els problemes següents. Solucions enteres de sistemes d'equacions lineals. Els darrers anys s'han obtingut resultats pel que fa a l’existència de llindars per a determinades solucions enteres a un sistema arbitrari d'equacions lineals donat, responent a la pregunta de quan s'espera que el subconjunt aleatori binomial d'un conjunt inicial de nombres enters contingui solucions gairebé sempre. La següent pregunta lògica és la següent. Suposem que estem en la zona en que hi haurà solucions enteres en el conjunt aleatori binomial, com es distribueixen aleshores aquestes solucions? Al capítol 1, avançarem per respondre aquesta pregunta proporcionant condicions suficients per a quan una gran varietat de solucions segueixen una distribució normal. També parlarem de com, en determinats casos, aquestes condicions suficients també són necessàries. Conjunts amb suma acotada. Què es pot dir de l'estructura de dos conjunts finits en un grup abelià si la seva suma de Minkowski no és molt més gran que la dels conjunts? Un resultat clàssic de Kneser diu que això pot passar si i només si la suma de Minkowski és periòdica respecte a un subgrup propi. En el capítol 3 establirem dos tipus de resultats. En primer lloc, establirem les anomenades versions robustes dels teoremes clàssics de Kneser i Freiman. Robust aquí es refereix al fet que en comptes de demanar informació estructural sobre els conjunts constituents amb el coneixement que la seva suma és petita, només necessitem que això sigui vàlid per a un subconjunt gran passa si només volem donar una informació estructural per a gairebé tots els parells de conjunts amb una suma d'una mida determinada? Donem un teorema d'estructura aproximat que s'aplica a gairebé la majoria dels rangs possibles per la mida dels conjunts suma. Sistemes de conjunts de Sidon. Les preguntes clàssiques sobre els conjunts de Sidon són determinar la seva mida màxima o saber quan un conjunt aleatori és un conjunt de Sidon. Al capítol 4 generalitzem la noció de conjunts de Sidon per establir sistemes i establim els límits corresponents per a aquestes dues preguntes. També demostrem un resultat de densitat relativa, resultat condicionat a una conjectura sobre l'estructura específica dels sistemes màxims de Sidon. Conjunts independents en hipergrafs. El mètode dels contenidors d'hipergrafs és una eina general que es pot utilitzar per obtenir resultats sobre el nombre i l'estructura de conjunts independents en els hipergrafs. La connexió amb la combinatòria additiva apareix perquè molts problemes additius es poden codificar com l'estudi de conjunts independents en hipergrafs.
Matemàtica aplicada

In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.

We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

This volume contains eight survey articles by the invited speakers of the 29th British Combinatorial Conference, held at Lancaster University in July 2022. Each article provides an overview of recent developments in a current hot research topic in combinatorics. These topics span graphs and hypergraphs, Latin squares, linear programming, finite fields, extremal combinatorics, Ramsey theory, graph minors and tropical geometry. The authors are among the world's foremost researchers on their respective topics but their surveys are aimed at nonspecialist readers: they are written clearly with little prior knowledge assumed and with pointers to the wider literature. Taken together these surveys give a snapshot of the research frontier in contemporary combinatorics, making the latest developments accessible to researchers and graduate students in mathematics and theoretical computer science with an interest in combinatorics and helping them to keep abreast of the field.