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

A proof of the Upper Matching Conjecture for large graphs

225   0   0.0 ( 0 )
 نشر من قبل Will Perkins
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




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

We prove that the `Upper Matching Conjecture of Friedland, Krop, and Markstrom and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every $d$ and every large enough $n$ divisible by $2d$, a union of $n/(2d)$ copies of the complete $d$-regular bipartite graph maximizes the number of independent sets and matchings of size $k$ for each $k$ over all $d$-regular graphs on $n$ vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.



قيم البحث

اقرأ أيضاً

A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$.
86 - Marino Romero 2020
In the context of the (generalized) Delta Conjecture and its compositional form, DAdderio, Iraci, and Wyngaerd recently stated a conjecture relating two symmetric function operators, $D_k$ and $Theta_k$. We prove this Theta Operator Conjecture, findi ng it as a consequence of the five-term relation of Mellit and Garsia. As a result, we find surprising ways of writing the $D_k$ operators.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
A computer search through the oriented matroid programs with dimension 5 and 10 facets shows that the maximum strictly monotone diameter is 5. Thus $Delta_{sm}(5,10)=5$. This enumeration is analogous to that of Bremner and Schewe for the non-monotone diameter of 6-polytopes with 12 facets. Similar enumerations show that $Delta_{sm}(4,9)=5$ and $Delta_m(4,9)=Delta_m(5,10)=6.$ We shorten the known non-computer proof of the strict monotone 4-step conjecture.
123 - Lei Xue 2020
In 1967, Grunbaum conjectured that any $d$-dimensional polytope with $d+sleq 2d$ vertices has at least [phi_k(d+s,d) = {d+1 choose k+1 }+{d choose k+1 }-{d+1-s choose k+1 } ] $k$-faces. We prove this conjecture and also characterize the cases in which equality holds.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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