تقرير
The maximum length of $K_r$-Bootstrap Percolation
| العنوان: | The maximum length of $K_r$-Bootstrap Percolation |
|---|---|
| المؤلفون: | Balogh, József, Kronenberg, Gal, Pokrovskiy, Alexey, Szabó, Tibor |
| سنة النشر: | 2019 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05D99, 05C35, 82B43, 11B25 |
| الوصف: | Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollob\'as in 1968. In this process, we start with initial "infected" set of edges $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t\subseteq E(K_n)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n],E_t\cup e)$. A question raised by Bollob\'as asks for the maximum time the process can run before it stabilizes. Bollob\'as, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H=K_r$. They answered the question for $r\leq 4$ and gave a non-trivial lower bound for every $r\geq 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. In this paper we disprove their conjecture for every $r\geq 6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction. Comment: 10 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1907.04559 |
| رقم الأكسشن: | edsarx.1907.04559 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |