Let
On the discrepancy of random low degree set systems
Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there are
- NSF-PAR ID:
- 10161536
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 695-705
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
denote the power set of [ n ], ordered by inclusion, and letdenote the random poset obtained from by retaining each element from independently at random with probability p and discarding it otherwise. Givenany fixed posetF we determine the threshold for the property thatcontains F as an induced subposet. We also asymptotically determine the number of copies of a fixed posetF in. Finally, we obtain a number of results on the Ramsey properties of the random poset . -
more » « less
Abstract A graph is said to be
‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphis asymptotically almost surely ‐universal for , a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that is almost surely ‐universal for . -
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 In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on
with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o (n )). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem. -
more » « less
Abstract We prove that a WLD subspace of the space
consisting of all bounded, countably supported functions on a set Γ embeds isomorphically into if and only if it does not contain isometric copies of . Moreover, a subspace of is constructed that has an unconditional basis, does not embed into , and whose every weakly compact subset is separable (in particular, it cannot contain any isomorphic copies of ).
