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
-
Abstract Incorporating wave energy converters (WECs) into existing oceanographic instrument systems and offshore floating platforms can not only enhance the performance of these applications but reduce operational expenses. This article studies a system integrating a floater WEC with a floating spar platform via the inerter pendulum vibration absorber with a power take-off (IPVA-PTO) mechanism, with a focus on random wave excitation. Experiments and simulations performed on a simplified system in which the WEC is held fixed and radiation damping is absent reveal that the power spectral density (PSD) of the system consists of odd-order superharmonics when the peak frequency of wave excitation is equal to the natural frequency of the system. It is found that the odd-order superharmonics are created by the IPVA and have a strong correlation with an enhancement in power output. Simulations without the aforementioned simplifications confirm the odd-order superharmonics and the correlation, and demonstrate an improvement in the capture width ratio (CWR) of 161.4% at resonance without compromising the response amplitude operator (RAO) of the spar, in comparison with a linear benchmark with optimal electrical damping.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21147
