ترغب بنشر مسار تعليمي؟ اضغط هنا

A short proof of the blow-up lemma for approximate decompositions

64   0   0.0 ( 0 )
 نشر من قبل Stefan Ehard
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

Kim, Kuhn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655--4742) greatly extended the well-known blow-up lemma of Komlos, Sarkozy and Szemeredi by proving a `blow-up lemma for approximate decompositions which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kuhn and Osthus to prove the tree packing conjecture due to Gyarfas and Lehel from 1976 and Ringels conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kuhn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties so that it can be combined with Keevashs results on designs to obtain results of the following form. For all $varepsilon>0$, $rin mathbb{N}$ and all large $n$ (such that $r$ divides $n-1$), there is a decomposition of $K_n$ into any collection of $r$-regular graphs $H_1,ldots,H_{(n-1)/r}$ on $n$ vertices provided that $H_1,ldots,H_{varepsilon n}$ contain each at least $varepsilon n$ vertices in components of size at most $varepsilon^{-1}$.



قيم البحث

اقرأ أيضاً

We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to longstanding decomposition problems. For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,dots,H_s$ are bounded degree $n$-vertex graphs with $sum_{i=1}^{s} e(H_i) leq (1-o(1)) e(G)$. Then $H_1,dots,H_s$ can be packed edge-disjointly into $G$. The case when $G$ is the complete graph $K_n$ implies an approximate version of the tree packing conjecture of Gyarfas and Lehel for bounded degree trees, and of the Oberwolfach problem. We provide a more general version of the above approximate decomposition result which can be applied to super-regular graphs and thus can be combined with Szemeredis regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlos, SarkH{o}zy and Szemeredi to the setting of approximate decompositions.
A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Komlos, Sarkozy and Szemeredi that applies to almost optimally bounded colourings. A corollary of this is that there exists a rainbow copy of any bounded-degree spanning subgraph $H$ in a quasirandom host graph $G$, assuming that the edge-colouring of $G$ fulfills a boundedness condition that is asymptotically best possible. This has many applications beyond rainbow colourings, for example to graph decompositions, orthogonal double covers and graph labellings.
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three spar
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly per fect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا