|
Combinatorics, Probability and Computing
Journal Prestige (SJR): 0.839  Citation Impact (citeScore): 1 Number of Followers: 4  Hybrid journal (It can contain Open Access articles)ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [387 journals]
|
- Positive association of the oriented percolation cluster in randomly
oriented graphs- Authors: François Bienvenu
Pages: 811 - 815
Abstract: Consider any fixed graph whose edges have been randomly and independently oriented, and write {S ⇝} to indicate that there is an oriented path going from a vertex s ∊ S to vertex i. Narayanan (2016) proved that for any set S and any two vertices i and j, {S ⇝ i} and {S ⇝ j} are positively correlated. His proof relies on the Ahlswede–Daykin inequality, a rather advanced tool of probabilistic combinatorics.In this short note I give an elementary proof of the following, stronger result: writing V for the vertex set of the graph, for any source set S, the events {S ⇝ i}, i ∊ V, are positively associated, meaning that the expectation of the product of increasing functionals of the family {S ⇝ i} for i ∊ V is greater than the product of their expectations.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000191
Issue No: Vol. 28, No. 6 (2019)
- Authors: François Bienvenu
- A natural barrier in random greedy hypergraph matching
- Authors: Patrick Bennett; Tom Bohman
Pages: 816 - 825
Abstract: Let r ⩾ 2 be a fixed constant and let
$ {\cal H} $ be an r-uniform, D-regular hypergraph on N vertices. Assume further that D → ∞ as N → ∞ and that degrees of pairs of vertices in 
$ {\cal H} $ are at most L where L = D/( log N)ω(1). We consider the random greedy algorithm for forming a matching in 
$ {\cal H} $ . We choose a matching at random by iteratively choosing edges uniformly at random to be in the matching and deleting all edges that share at least one vertex with a chosen edge before moving on to the next choice. This process terminates when there are no edges remaining in the graph. We show that with high probability the proportion of vertices of 
$ {\cal H} $ that are not saturated by the final matching is at most (L/D)(1/(2(r−1)))+o(1). This point is a natural barrier in the analysis of the random greedy hypergraph matching process.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000051
Issue No: Vol. 28, No. 6 (2019)
- Authors: Patrick Bennett; Tom Bohman
- On the union of intersecting families
- Authors: David Ellis; Noam Lifshitz
Pages: 826 - 839
Abstract: A family of sets is said to be intersecting if any two sets in the family have non-empty intersection. In 1973, Erdős raised the problem of determining the maximum possible size of a union of r different intersecting families of k-element subsets of an n-element set, for each triple of integers (n, k, r). We make progress on this problem, proving that for any fixed integer r ⩾ 2 and for any
$$k \le ({1 \over 2} - o(1))n$$ , if X is an n-element set, and 
$${\cal F} = {\cal F}_1 \cup {\cal F}_2 \cup \cdots \cup {\cal F}_r $$ , where each 
$$ {\cal F}_i $$ is an intersecting family of k-element subsets of X, then 
$$|{\cal F}| \le \left( {\matrix{n \cr k \cr } } \right) - \left( {\matrix{{n - r} \cr k \cr } } \right)$$ , with equality only if 
$${\cal F} = \{ S \subset X:|S| = k,\;S \cap R \ne \emptyset \} $$ for some R ⊂ X with |R| = r. This is best possible up to the size of the o(1) term, and improves a 1987 result of Frankl and Füredi, who obtained the same conclusion under the stronger hypothesis 
$$k < (3 - \sqrt 5 )n/2$$ , in the case r = 2. Our proof utilizes an isoperimetric, influence-based method recently developed by Keller and the authors.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S096354831900004X
Issue No: Vol. 28, No. 6 (2019)
- Authors: David Ellis; Noam Lifshitz
- k-Partite+
Cycles- Authors: Wei Gao; Jie Han, Yi Zhao
Pages: 840 - 870
Abstract: Given two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K(k)(1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S096354831900021X
Issue No: Vol. 28, No. 6 (2019)
- Authors: Wei Gao; Jie Han, Yi Zhao
- On the Size-Ramsey Number of Cycles
- Authors: R. Javadi; F. Khoeini, G. R. Omidi, A. Pokrovskiy
Pages: 871 - 880
Abstract: For given graphs G1,…, Gk, the size-Ramsey number
$\hat R({G_1}, \ldots ,{G_k})$ is the smallest integer m for which there exists a graph H on m edges such that in every k-edge colouring of H with colours 1,…,k, H contains a monochromatic copy of Gi of colour i for some 1 ≤ i ≤ k. We denote 
$\hat R({G_1}, \ldots ,{G_k})$ by 
${\hat R_k}(G)$ when G1 = ⋯ = Gk = G.Haxell, Kohayakawa and Łuczak showed that the size-Ramsey number of a cycle Cn is linear in n, 
${\hat R_k}({C_n}) \le {c_k}n$ for some constant ck. Their proof, however, is based on Szemerédi’s regularity lemma so no specific constant ck is known.In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We provide an alternative proof of 
${\hat R_k}({C_n}) \le {c_k}n$ , avoiding use of the regularity lemma, where ck is exponential and doubly exponential in k, when n is even and odd, respectively. In particular, we show that for sufficiently large n we have 
${\hat R_2}({C_n}) \le {10^5} \times cn$ , where c = 6.5 if n is even and c = 1989 otherwise.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000221
Issue No: Vol. 28, No. 6 (2019)
- Authors: R. Javadi; F. Khoeini, G. R. Omidi, A. Pokrovskiy
- On Erdős–Ko–Rado for random hypergraphs I
- Authors: A. Hamm; J. Kahn
Pages: 881 - 916
Abstract: A family of sets is intersecting if no two of its members are disjoint, and has the Erdős–Ko–Rado property (or is EKR) if each of its largest intersecting subfamilies has non-empty intersection.Denote by
${{\cal H}_k}(n,p)$ the random family in which each k-subset of {1, …, n} is present with probability p, independent of other choices. A question first studied by Balogh, Bohman and Mubayi asks:
\begin{equation} {\rm{For what }}p = p(n,k){\rm{is}}{{\cal H}_k}(n,p){\rm{likely to be EKR}}? \end{equation} Here, for fixed c < 1/4, and 
$k \lt \sqrt {cn\log n} $ we give a precise answer to this question, characterizing those sequences p = p(n, k) for which
\begin{equation} {\mathbb{P}}({{\cal H}_k}(n,p){\rm{is EKR}}{\kern 1pt} ) \to 1{\rm{as }}n \to \infty . \end{equation}
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000117
Issue No: Vol. 28, No. 6 (2019)
- Authors: A. Hamm; J. Kahn
- Erratum to ‘On Percolation and the Bunkbed Conjecture’
- Authors: Svante Linusson
Pages: 917 - 918
Abstract: There was an incorrect argument in the proof of the main theorem in ‘On percolation and the bunkbed conjecture’, in Combin. Probab. Comput. (2011) 20 103–117 doi: 10.1017/S0963548309990666. I thus no longer claim to have a proof for the bunkbed conjecture for outerplanar graphs.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000038
Issue No: Vol. 28, No. 6 (2019)
- Authors: Svante Linusson
- Logarithmic Sobolev inequalities in discrete product spaces
- Authors: Katalin Marton
Pages: 919 - 935
Abstract: The aim of this paper is to prove an inequality between relative entropy and the sum of average conditional relative entropies of the following form: for a fixed probability measure q on
, (
is a finite set), and any probability measure 
on ,(*)
$$D(p||q){\rm{\le}}C \cdot \sum\limits_{i = 1}^n {{\rm{\mathbb{E}}}_p D(p_i ( \cdot |Y_1 ,{\rm{ }}...,{\rm{ }}Y_{i - 1} ,{\rm{ }}Y_{i + 1} ,...,{\rm{ }}Y_n )||q_i ( \cdot |Y_1 ,{\rm{ }}...,{\rm{ }}Y_{i - 1} ,{\rm{ }}Y_{i + 1} ,{\rm{ }}...,{\rm{ }}Y_n )),} $$ where pi(· |y1, …, yi−1, yi+1, …, yn) and qi(· |x1, …, xi−1, xi+1, …, xn) denote the local specifications for p resp. q, that is, the conditional distributions of the ith coordinate, given the other coordinates. The constant C depends on (the local specifications of) q.The inequality (*) ismeaningful in product spaces, in both the discrete and the continuous case, and can be used to prove a logarithmic Sobolev inequality for q, provided uniform logarithmic Sobolev inequalities are available for qi(· |x1, …, xi−1, xi+1, …, xn), for all fixed i and fixed (x1, …, xi−1, xi+1, …, xn). Inequality (*) directly implies that the Gibbs sampler associated with q is a contraction for relative entropy.In this paper we derive inequality (*), and thereby a logarithmic Sobolev inequality, in discrete product spaces, by proving inequalities for an appropriate Wasserstein-like distance.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000099
Issue No: Vol. 28, No. 6 (2019)
- Authors: Katalin Marton
- An Improved Upper Bound for Bootstrap Percolation in All Dimensions
- Authors: Andrew J. Uzzell
Pages: 936 - 960
Abstract: In r-neighbour bootstrap percolation on the vertex set of a graph G, a set A of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least r previously infected neighbours. When the elements of A are chosen independently with some probability p, it is natural to study the critical probability pc(G, r) at which it becomes likely that all of V(G) will eventually become infected. Improving a result of Balogh, Bollobás and Morris, we give a bound on the second term in the expansion of the critical probability when G = [n]d and d ⩾ r ⩾ 2. We show that for all d ⩾ r ⩾ 2 there exists a constant cd,r > 0 such that if n is sufficiently large, then
$$p_c (\left[ n \right]^d ,{\rm{ }}r){\rm{\le }}\left( {\frac{{\lambda (d,r)}}{{\log _{(r - 1)} (n)}} - \frac{{c_{d,r} }}{{(\log _{(r - 1)} (n))^{3/2} }}} \right)^{d - r + 1} ,$$ where λ(d, r) is an exact constant and log(k) (n) denotes the k-times iterated natural logarithm of n.
PubDate: 2019-11-01T00:00:00.000Z
DOI: 10.1017/S0963548319000130
Issue No: Vol. 28, No. 6 (2019)
- Authors: Andrew J. Uzzell
