BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Denote by Hk(n,p) the random k-graph in which each k-subset of {1...n} is present with probability p, independent of other choices. More or less answering a question of Balogh, Bohman and Mubayi, we show: there is a fixed ε>0 such that if n=2k+1 and p>1−ε, then w.h.p. (that is, with probability tending to 1 as k→∞), Hk(n,p) has the "Erdős-Ko-Rado property." We also mention a similar random version of Sperner's Theorem.
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 nonempty intersection. Denote by Hk(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: \[ \mbox{for what $p=p(n,k)$ is $\mathcal{H}_k(n,p)$ likely to be EKR?} \] Here, for fixed c<1/4, and k<cnlogn we give a precise answer to this question, characterizing those sequences p=p(n,k) for which Pr(Hk(n,p) is EKR)→1 as n→∞.
Settling a first case of a conjecture of M. Kahle on the homology of the clique complex of the random graph G=Gn,p, we show, roughly speaking, that (with high probability) the triangles of G span its cycle space whenever each of its edges lies in a triangle (which happens (w.h.p.) when p is at least about (3/2)lnn/n, and not below this unless p is very small.) We give two related proofs of this statement, together with a relatively simple proof of a fundamental "stability" theorem for triangle-free subgraphs of Gn,p, originally due to Kohayakawa, Łuczak and Rödl, that underlies the first of our proofs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.