We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in
Disproof of a packing conjecture of Alon and Spencer
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph
- Award ID(s):
- 1502650
- NSF-PAR ID:
- 10114264
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 55
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 531-544
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
( n, p ) for nearly optimalp (up to afactor). In particular, we show that given t = (1 −o (1))np Hamilton cyclesC 1,…,C t , each of which is oriented arbitrarily, a digraph∼ ( n, p ) w.h.p. contains edge disjoint copies ofC 1,…,C t , provided. We also show that given an arbitrarily oriented n ‐vertex cycleC , a random digraph∼ ( n, p ) w.h.p. contains (1 ±o (1))n !p n copies ofC , provided. -
more » « less
Abstract Let
be the random directed graph on n vertices where each of thepossible arcs is present independently with probability p . A celebrated result of Frieze shows that ifthen typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in is typically . We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typically directed Hamilton cycles. -
more » « less
Abstract We study a new geometric bootstrap percolation model,
line percolation , on thed ‐dimensional integer grid. In line percolation with infection parameter r , infection spreads from a subsetof initially infected lattice points as follows: if there exists an axis‐parallel line L withr or more infected lattice points on it, then every lattice point ofon L gets infected, and we repeat this until the infection can no longer spread. The elements of the setA are usually chosen independently, with some densityp , and the main question is to determine, the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine up to a multiplicative factor of and up to a multiplicative constant as for every fixed . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter. -
more » « less
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Let
n ≥ 2. Suppose a subset Ω ofn ‐dimensional Euclidean spacesatisfies −Ω = Ω c and Ω +v = Ωc (up to measure zero sets) for every standard basis vector. For any and for any q ≥ 1, letand let . For any x ∈∂ Ω, letN (x ) denote the exterior normal vector atx such that ‖N (x )‖2 = 1. Let. Our main result shows that B has the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular, Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10−9would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture. -
more » « less
Abstract We present a flow law for dislocation‐dominated creep in wet quartz derived from compiled experimental and field‐based rheological data. By integrating the field‐based data, including independently calculated strain rates, deformation temperatures, pressures, and differential stresses, we add constraints for dislocation‐dominated creep at conditions unattainable in quartz deformation experiments. A Markov Chain Monte Carlo (MCMC) statistical analysis computes internally consistent parameters for the generalized flow law:
= Aσ n e −(Q +V P)/RT . From this initial analysis, we identify differenteffective stress exponents for quartz deformed at confining pressures above and below ∼700 MPa. To minimize the possible effect of confining pressure, compiled data are separated into “low‐pressure” (<560 MPa) and “high‐pressure” (700–1,600 MPa) groups and reanalyzed using the MCMC approach. The “low‐pressure” data set, which is most applicable at midcrustal to lower‐crustal confining pressures, yields the following parameters: log(A ) = −9.30 ± 0.66 MPa−n −r s−1;n = 3.5 ± 0.2;r = 0.49 ± 0.13;Q = 118 ± 5 kJ mol−1; andV = 2.59 ± 2.45 cm3 mol−1. The “high‐pressure” data set produces a different set of parameters: log(A ) = −7.90 ± 0.34 MPa−n −r s−1;n = 2.0 ± 0.1;r = 0.49 ± 0.13;Q = 77 ± 8 kJ mol−1; andV = 2.59 ± 2.45 cm3 mol−1. Predicted quartz rheology is compared to other flow laws for dislocation creep; the calibrations presented in this study predict faster strain rates under geological conditions by more than 1 order of magnitude. The change inn at high confining pressure may result from an increase in the activity of grain size sensitive creep.
