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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

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

Název periodika

Combinatorics, Probability &amp; Computing

ISSN

0963-5483

e-ISSN

—

Svazek periodika

26

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

17

Strana od-do

406-422

Kód UT WoS článku

000398967400004

EID výsledku v databázi Scopus

—