An official website of the United States government
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.
more »
« less
Regularity method and large deviation principles for the Erdős–Rényi hypergraph
We develop a quantitative large deviations theory for random hypergraphs, which rests on tensor decomposition and counting lemmas under a novel family of cut-type norms. As our main application, we obtain sharp asymptotics for joint upper and lower tails of homomorphism counts in the r-uniform Erdo ̋s–Rényi hypergraph for any fixed r≥2, generalizing and improving on previous results for the Erdo ̋s–Rényi graph (r=2). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields tail asymptotics for other nonlinear functionals, such as induced homomorphism counts.
more »
« less
- PAR ID:
- 10530840
- Publisher / Repository:
- Project Euclid
- Date Published:
- Journal Name:
- Duke Mathematical Journal
- Volume:
- 173
- Issue:
- 5
- ISSN:
- 0012-7094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An $(n,r,s)$-system is an $$r$$-uniform hypergraph on $$n$$ vertices such that every pair of edges has an intersection of size less than $$s$$. Using probabilistic arguments, Rödl and Šiňajová showed that for all fixed integers $$r> s \ge 2$$, there exists an $(n,r,s)$-system with independence number $$O\left(n^{1-\delta+o(1)}\right)$$ for some optimal constant $$\delta >0$$ only related to $$r$$ and $$s$$. We show that for certain pairs $(r,s)$ with $$s\le r/2$$ there exists an explicit construction of an $(n,r,s)$-system with independence number $$O\left(n^{1-\epsilon}\right)$$, where $$\epsilon > 0$$ is an absolute constant only related to $$r$$ and $$s$$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman.more » « less
-
One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $$n$$-vertex graph with more than $$\frac{k-1}{2}n$$ edges contains any $$k$$-edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $$r$$-uniform hypergraph, i.e., a hypergraph where each edge contains $$r$$ vertices. A tight tree is an $$r$$-uniform hypergraph such that there is an ordering $$v_1,\ldots,v_n$$ of its its vertices with the following property: the vertices $$v_1,\ldots,v_r$$ form an edge and for every $i>r$, there is a single edge $$e$$ containing the vertex $$v_i$$ and $r-1$ of the vertices $$v_1,\ldots,v_{i-1}$$, and $$e\setminus\{v_i\}$$ is a subset of one of the edges consisting only of vertices from $$v_1,\ldots,v_{i-1}$$. The conjecture of Kalai asserts that every $$n$$-vertex $$r$$-uniform hypergraph with more than $$\frac{k-1}{r}\binom{n}{r-1}$$ edges contains every $$k$$-edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $$n$$ for every $$r$$ and $$k$$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $$r$$-tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous Erdős-Gallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first non-trivial upper bound valid for all $$r$$ and $$k$$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less
-
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any r-edge colouring of Kn? We consider how big a connected component can we guarantee in any r-edge colouring of Kn if we allow ourselves to use up to s colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a k-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided n is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. We also consider a generalisation in a similar direction of a question first considered by Erdős and Rényi in 1956, who considered given n and m, what is the smallest number of m-cliques which can cover all edges of Kn? This problem is essentially equivalent to the question of what is the minimum number of vertices that are certain to be incident to at least one edge of some colour in any r-edge colouring of Kn. We consider what happens if we allow ourselves to use up to s colours. We obtain a more complete understanding of the answer to this question for large n, in particular determining it up to a constant factor for all 1≤s≤r, as well as obtaining much more precise results for various ranges including the correct asymptotics for essentially the whole range.more » « less
-
A graph $$G$$ percolates in the $$K_{r,s}$$-bootstrap process if we can add all missing edges of $$G$$ in some order such that each edge creates a new copy of $$K_{r,s}$$, where $$K_{r,s}$$ is the complete bipartite graph. We study $$K_{r,s}$$-bootstrap percolation on the Erdős-Rényi random graph, and determine the percolation threshold for balanced $$K_{r,s}$$ up to a logarithmic factor. This partially answers a question raised by Balogh, Bollobás, and Morris. We also establish a general lower bound of the percolation threshold for all $$K_{r,s}$$, with $$r\geq s \geq 3$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1215/00127094-2023-0029
