ﻻ يوجد ملخص باللغة العربية
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
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
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
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.