Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10369990" target="_blank" >RIV/00216208:11320/17:10369990 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1017/S0963548316000420" target="_blank" >http://dx.doi.org/10.1017/S0963548316000420</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1017/S0963548316000420" target="_blank" >10.1017/S0963548316000420</a>

Result language

angličtina

Original language name

Erdos-Ko-Rado for Random Hypergraphs: Asymptotics and Stability

Original language description

We investigate the asymptotic version of the Erdos-Ko-Rado theorem for the random k-uniform hypergraph H-k(n, p). For 2 &lt;= k(n) &lt;= n/2, let N = (n/k) and D = (n-k/k). We show that with probability tending to 1 as n -&gt; infinity, the largest intersecting subhypergraph of Hk( n, p) has size (1+o(1))p(n)(k)-N for any p &gt;&gt; n/k ln(2) (n/k) D-1. This lower bound on p is asymptotically best possible for k = Theta(n). For this range of k and p, we are able to show stability as well. A different behaviour occurs when k = o(n). In this case, the lower bound on p is almost optimal. Further, for the small interval D-1 &lt;&lt; p &lt;&lt; ( n/k)1(-epsilon)D(-1), the largest intersecting subhypergraph of Hk(n, p) has size Theta(ln(pD) ND-1), provided that k &gt;&gt; root nlnn. Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in H-k(n, p), for essentially all values of p and k.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2017

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Combinatorics, Probability &amp; Computing

ISSN

0963-5483

e-ISSN

—

Volume of the periodical

26

Issue of the periodical within the volume

3

Country of publishing house

GB - UNITED KINGDOM

Number of pages

17

Pages from-to

406-422

UT code for WoS article

000398967400004

EID of the result in the Scopus database

—