تقرير
Clique Decompositions in Random Graphs via Refined Absorption
| العنوان: | Clique Decompositions in Random Graphs via Refined Absorption |
|---|---|
| المؤلفون: | Delcourt, Michelle, Kelly, Tom, Postle, Luke |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05B05, 05B07, 05C80 |
| الوصف: | We prove that if $p\ge n^{-\frac{1}{3}+\beta}$ for some $\beta > 0$, then asymptotically almost surely the binomial random graph $G(n,p)$ has a $K_3$-packing containing all but at most $n + O(1)$ edges. Similarly, we prove that if $d \ge n^{\frac{2}{3}+\beta}$ for some $\beta > 0$ and $d$ is even, then asymptotically almost surely the random $d$-regular graph $G_{n,d}$ has a triangle decomposition provided $3 \mid d \cdot n$. We also show that $G(n,p)$ admits a fractional $K_3$-decomposition for such a value of $p$. We prove analogous versions for a $K_q$-packing of $G(n,p)$ with $p\ge n^{-\frac{1}{q+0.5}+\beta}$ and leave of $(q-2)n+O(1)$ edges, for $K_q$-decompositions of $G_{n,d}$ with $(q-1)~|~d$ and $d\ge n^{1-\frac{1}{q+0.5}+\beta}$ provided $q\mid d\cdot n$, and for fractional $K_q$-decompositions. Comment: 49 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2402.17857 |
| رقم الأكسشن: | edsarx.2402.17857 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |