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
This content will become publicly available on November 1, 2025
Robertson’s conjecture and universal finite generation in the homology of graph braid groups
Abstract We formulate a categorification of Robertson’s conjecture analogous to the categorical graph minor conjecture of Miyata–Proudfoot–Ramos. We show that these conjectures imply the existence of a finite list of atomic graphs generating the homology of configuration spaces of graphs—in fixed degree, with a fixed number of particles, under topological embeddings. We explain how the simplest case of our conjecture follows from work of Barter and Proudfoot–Ramos, implying that the category of cographs is Noetherian, a result of potential independent interest.
more »
« less
- Award ID(s):
- 2400460
- PAR ID:
- 10560137
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Selecta Mathematica
- Volume:
- 30
- Issue:
- 5
- ISSN:
- 1022-1824
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Given a fixed graph H, what is the (exponentially small) probability that the number XHof copies of Hin the binomial random graph Gn,pis at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.more » « less
-
Kumar, Amit; Ron-Zewi, Noga (Ed.)We study the worst-case mixing time of the global Kawasaki dynamics for the fixed-magnetization Ising model on the class of graphs of maximum degree Δ. Proving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that below the tree uniqueness threshold, the Kawasaki dynamics mix rapidly for all magnetizations. Disproving a conjecture of Carlson, Davies, Kolla, and Perkins, we show that the regime of fast mixing does not extend throughout the regime of tractability for this model: there is a range of parameters for which there exist efficient sampling algorithms for the fixed-magnetization Ising model on max-degree Δ graphs, but the Kawasaki dynamics can take exponential time to mix. Our techniques involve showing spectral independence in the fixed-magnetization Ising model and proving a sharp threshold for the existence of multiple metastable states in the Ising model with external field on random regular graphs.more » « less
-
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. ’06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles our small conjecture [SODA ’21] in the case of ordered graphs.more » « less
-
A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.more » « less
