اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA short proof that ``proper = unit
95
0
0.0
(
0
)
تأليف
Kenneth P. Bogart
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
قيم البحث
اقرأ أيضاً
We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval o
rders, where the class of proper interval orders is exactly the same as the class of unit interval orders.
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.
We give a combinatorial proof that the product of a Schubert polynomial by a Schur polynomial is a nonnegative sum of Schubert polynomials. Our proof uses Assafs theory of dual equivalence to show that a quasisymmetric function of Bergeron and Sottil
e is Schur-positive. By a geometric comparison theorem of Buch and Mihalcea, this implies the nonnegativity of Gromov-Witten invariants of the Grassmannian.
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 qu
asirandom 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}$.
In 1998 the second author proved that there is an $epsilon>0$ such that every graph satisfies $chi leq lceil (1-epsilon)(Delta+1)+epsilonomegarceil$. The first author recently proved that any graph satisfying $omega > frac 23(Delta+1)$ contains a sta
ble set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Halls Theorem, Brooks Theorem, the Lovasz Local Lemma, and Talagrands Inequality.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
