Extensions of barrier sets to nonzero roots of the matching polynomial

In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root θ of the matching polynomial, we define θ-barrier and θ-extreme sets. We prove a generalized Berge-Tutte formula and give a characterization for the set of all θ-special vertices in a graph.     

Evolutionary insights on the willingness to communicate

While in previous models of pre-play communication players are forced to communicate, we investigate what happens if players can choose not to participate in this cheap talk. Outcomes are predicted by analyzing evolutionary stability in a population of a priori identical players. If the game following the communication rewards players who choose the same action then an efficient outcome is only guaranteed when participation in the pre-play communication is voluntary. If however players aim to coordinate on choosing different actions in the underlying game and there are sufficiently many messages then the highest payoff is selected when players are forced to talk to each other before playing the game. Received: September 2000/Revised: March 2003     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

Number of zeros of interval polynomials

In this paper, we develop a rigorous algorithm for counting the real interval zeros of polynomials with perturbed coefficients that lie within a given interval, without computing the roots of any polynomials. The result generalizes Sturm’s Theorem for counting the roots of univariate polynomials to univariate interval polynomials.     

The symmetric Meixner-Pollaczek polynomials with real parameter

The Symmetric Meixner-Pollaczek polynomials for λ>0 are well-studied polynomials. These are polynomials orthogonal on the real line with respect to a continuous, positive real measure. For λ?0, are also polynomials, however they are not orthogonal on the real line with respect to any real measure. This paper defines a non-standard inner product with respect to which the polynomials for λ?0, become orthogonal polynomials. It examines the major properties of the polynomials, for λ>0 which are also shared by the polynomials, for λ?0.     

计算Bezout矩阵惯性的一个快速方法及其应用

本文给出了求Bezout矩阵的惯性的一个快速的无除方法,并且由此方法可很快得出一个整系数多项式方程的不同实根个数及不同对共轭复根的对数。     

Two problems on independent sets in graphs

Let i_t(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (i_t(G))_t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for .We also consider the problem of estimating i(G)=∑_t≥0i_t(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by K_δ,n−δ, the complete bipartite graph with δ vertices in one partition class and n−δ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑_t≥0i_t(G)x^t≤∑_t≥0i_t(K_δ,n−δ)x^t with equality if and only if G=K_δ,n−δ.     

Enumerative properties of shifted-Dyck partitions

We study the enumerative properties of a new class of (skew) shifted partitions. This class arises in the computation of certain parabolic Kazhdan-Lusztig polynomials and is closely related to ballot sequences. As consequences of our results, we obtain new identities for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs and for the ordinary Kazhdan-Lusztig polynomials of certain Weyl groups.     

Herschel图的匹配唯一性

研究了H erschel图的一些性质,以及它的匹配唯一性.     

关于Sturm定理的一点注记

经典的S turm定理用于判定多项式在给定区间上不同的实根个数,但是并不能刻画重根的情况.在这里定义了推广的S turm序列,将S turm定理进行一定地延拓,给出区间上多项式的所有实根均是偶重根或奇重根的充要条件.作为应用,讨论了多项式正(负)半定的判定问题.     

Dimensional results for Cartesian products of homogeneous Moran sets

M(J, {m _s * n _s }, {c _s }) be the collection of Cartesian products of two homogenous Moran sets with the same ratios {c _s } where J = [0, 1]×[0, 1]. Then the maximal and minimal values of the Hausdorff dimensions for the elements in M are obtained without any restriction on {m _s n _s } or {c _s }.