An official website of the United States government
Abstract How many copies of a fixed odd cycle, , can a planar graph contain? We answer this question asymptotically for and prove a bound which is tight up to a factor of 3/2 for all other values of . This extends the prior results of Cox and Martin and of Lv, Győri, He, Salia, Tompkins, and Zhu on the analogous question for even cycles. Our bounds result from a reduction to the following maximum likelihood question: which probability mass on the edges of some clique maximizes the probability that edges sampled independently from form either a cycle or a path?
more »
« less
Moderate deviations in cycle count
Abstract We prove moderate deviations bounds for the lower tail of the number of odd cycles in a random graph. We show that the probability of decreasing triangle density by , is whenever . These complement results of Goldschmidt, Griffiths, and Scott, who showed that for , the probability is . That is, deviations of order smaller than behave like small deviations, and deviations of order larger than behave like large deviations. We conjecture that a sharp change between the two regimes occurs for deviations of size , which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. We give analogous results for the ‐cycle density, for all odd . Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.
more »
« less
- Award ID(s):
- 2145800
- PAR ID:
- 10492770
- Editor(s):
- Bohman, T
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 63
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- 779 to 820
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Consider a gambler who on each bet either wins 1 with probability p or loses 1 with probability q=1-p, with the results of successive bets being independent. The gambler will stop betting when they are either up k or down k. Letting N be the number of bets made, we show that N is a new better than used random variable. Moreover, we show that if k is even then N/2 has an increasing failure rate, and if k is odd then (N+1)/2 has an increasing failure rate.more » « less
-
ABSTRACT The probability distribution of density in isothermal, supersonic, turbulent gas is approximately lognormal. This behaviour can be traced back to the shock waves travelling through the medium, which randomly adjust the density by a random factor of the local sonic Mach number squared. Provided a certain parcel of gas experiences a large number of shocks, due to the central limit theorem, the resulting distribution for density is lognormal. We explore a model in which parcels of gas undergo finite number of shocks before relaxing to the ambient density, causing the distribution for density to deviate from a lognormal. We confront this model with numerical simulations with various rms Mach numbers ranging from subsonic as low as 0.1 to supersonic at 25. We find that the fits to the finite formula are an order of magnitude better than a lognormal. The model naturally extends even to subsonic flows, where no shocks exist.more » « less
-
We present Lilac, a separation logic for reasoning about probabilistic programs where separating conjunction captures probabilistic independence. Inspired by an analogy with mutable state where sampling corresponds to dynamic allocation, we show how probability spaces over a fixed, ambient sample space appear to be the natural analogue of heap fragments, and present a new combining operation on them such that probability spaces behave like heaps and measurability of random variables behaves like ownership. This combining operation forms the basis for our model of separation, and produces a logic with many pleasant properties. In particular, Lilac has a frame rule identical to the ordinary one, and naturally accommodates advanced features like continuous random variables and reasoning about quantitative properties of programs. Then we propose a new modality based on disintegration theory for reasoning about conditional probability. We show how the resulting modal logic validates examples from prior work, and give a formal verification of an intricate weighted sampling algorithm whose correctness depends crucially on conditional independence structure.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21147
