اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlmost Unimodal and Real-Rooted Graph Polynomials
148
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It is well known that the coefficients of the matching polynomial are unimodal. Unimodality of the coefficients (or their absolute values) of other graph polynomials have been studied as well. One way to prove unimodality is to prove real-rootedness.` Recently I. Beaton and J. Brown (2020) proved the for almost all graphs the coefficients of the domination polynomial form a unimodal sequence, and C. Barton, J. Brown and D. Pike (2020) proved that the forest polynomial (aka acyclic polynomial) is real-rooted iff $G$ is a forest. Let $mathcal{A}$ be a graph property, and let $a_i(G)$ be the number of induced subgraphs of order $i$ of a graph $G$ which are in $mathcal{A}$. Inspired by their results we prove: {bf Theorem:} If $mathcal{A}$ is the complement of a hereditary property, then for almost all graphs in $G(n,p)$ the sequence $a_i(G)$ is unimodal. {bf Theorem:} If $mathcal{A}$ is a hereditary property which contains a graph which is not a clique or the complement of a clique, then the graph polynomial $P_{mathcal{A}}(G;x) = sum_i a_i(G) x^i$ is real-rooted iff $G in mathcal{A}$.
قيم البحث
اقرأ أيضاً
In 2009, Brown gave a set of conditions which when satisfied imply that a Feynman integral evaluates to a multiple zeta value. One of these conditions is called reducibility, which loosely says there is an order of integration for the Feynman integra
l for which Browns techniques will succeed. Reducibility can be abstracted away from the Feynman integral to just being a condition on two polynomials, the first and second Symanzik polynomials. These polynomials can be defined from graphs, and thus reducibility is a property of graphs. We prove that for a fixed number of external momenta and no masses, reducibility is graph minor closed, correcting the previously claimed proofs of this fact. A computational study of reducibility was undertaken by Bogner and L{u}ders who found that for graphs with $4$-on-shell momenta and no masses, $K_{4}$ with momenta on each vertex is a forbidden minor. We add to this and find that when we restrict to graphs with four on-shell external momenta the following graphs are forbidden minors: $K_{4}$ with momenta on each vertex, $W_{4}$ with external momenta on the rim vertices, $K_{2,4}$ with external momenta on the large side of the bipartition, and one other graph. We do not expect that these minors characterize reducibility, so instead we give structural characterizations of the graphs not containing subsets of these minors. We characterize graphs not containing a rooted $K_{4}$ or rooted $W_{4}$ minor, graphs not containing rooted $K_{4}$ or rooted $W_{4}$ or rooted $K_{2,4}$ minors, and also a characterization of graphs not containing all of the known forbidden minors. Some comments are made on graphs not containing $K_{3,4}$, $K_{6}$ or a graph related to Wagners graph as a minor.
A k-valuation is a special type of edge k-colouring of a medial graph. Various graph polynomials, such as the Tutte, Penrose, Bollobas-Riordan, and transition polynomials, admit combinatorial interpretations and evaluations as weighted counts of k-va
luations. In this paper, we consider a multivariate generating function of k-valuations. We show that this is a polynomial in k and hence defines a graph polynomial. We then show that the resulting polynomial has several desirable properties, including a recursive deletion-contraction-type definition, and specialises to the graph polynomials mentioned above. It also offers an alternative extension of the Penrose polynomial from plane graphs to graphs in other surfaces.
Recently, Choi and Park introduced an invariant of a finite simple graph, called signed a-number, arising from computing certain topological invariants of some specific kinds of real toric manifolds. They also found the signed a-numbers of path graph
s, cycle graphs, complete graphs, and star graphs. We introduce a signed a-polynomial which is a generalization of the signed a-number and gives a-, b-, and c-numbers. The signed a-polynomial of a graph $G$ is related to the Poincare polynomial $P_{M(G)}(z)$, which is the generating function for the Betti numbers of the real toric manifold $M(G)$. We give the generating functions for the signed a-polynomials of not only path graphs, cycle graphs, complete graphs, and star graphs, but also complete bipartite graphs and complete multipartite graphs. As a consequence, we find the Euler characteristic number and the Betti numbers of the real toric manifold $M(G)$ for complete multipartite graphs $G$.
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various pr
oducts, ranging from explicit formulae and recurrences for specific families to more general results. As an application, we show the domination polynomial is computationally hard to evaluate.
The binomial Eulerian polynomials, introduced by Postnikov, Reiner, and Williams, are $gamma$-positive polynomials and can be interpreted as $h$-polynomials of certain flag simplicial polytopes. Recently, Athanasiadis studied analogs of these polynom
ials for colored permutations. In this paper, we generalize them to $mathbf{s}$-inversion sequences and prove that these new polynomials have only real roots by the method of interlacing polynomials. Three applications of this result are presented. The first one is to prove the real-rootedness of binomial Eulerian polynomials, which confirms a conjecture of Ma, Ma, and Yeh. The second one is to prove that the symmetric decomposition of binomial Eulerian polynomials for colored permutations is real-rooted. Thirdly, our polynomials for certain $mathbf{s}$-inversion sequences are shown to admit a similar geometric interpretation related to edgewise subdivisions of simplexes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
