On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

Coalescing systems of non-Brownian particles

A well-known result of Arratia shows that one can make rigorous the notion of starting an independent Brownian motion at every point of an arbitrary closed subset of the real line and then building a set-valued process by requiring particles to coalesce when they collide. Arratia noted that the value of this process will be almost surely a locally finite set at all positive times, and a finite set almost surely if the initial value is compact: the key to both of these facts is the observation that, because of the topology of the real line and the continuity of Brownian sample paths, at the time when two particles collide one or the other of them must have already collided with each particle that was initially between them. We investigate whether such instantaneous coalescence still occurs for coalescing systems of particles where either the state space of the individual particles is not locally homeomorphic to an interval or the sample paths of the individual particles are discontinuous. We give a quite general criterion for a coalescing system of particles on a compact state space to coalesce to a finite set at all positive times almost surely and show that there is almost sure instantaneous coalescence to a locally finite set for systems of Brownian motions on the Sierpinski gasket and stable processes on the real line with stable index greater than one.     

Coalescing Particles on an Interval

At time 0, we begin with a particle at each integer in [0, n]. At each positive integer time, one of the particles remaining in [1, n] is chosen at random and moved one to the left, coalescing with any particle that might already be there. How long does it take until all particles coalesce (at 0)?     

Proof of a conjecture of Fiedler and Markham

Let A be an n×n nonsingular M-matrix. For the Hadamard product AA⁻¹, M. Fiedler and T.L. Markham conjectured in [Linear Algebra Appl. 10l (1988) 1] that q(AA⁻¹)2/n, where q(AA⁻¹) is the smallest eigenvalue (in modulus) of AA⁻¹. We considered this conjecture in [Linear Algebra Appl. 288 (1999) 259] having observed an incorrect proof in [Linear Algebra Appl. 144 (1991) 171] and obtained that q(AA⁻¹)(2/n)(n−1)/n. The present paper gives a proof for this conjecture.     

Coalescing and noncoalescing stochastic flows in R1

We study homogeneous stochastic flows, families X_st, 0 ⩽ s ⩽ t < ∞ of random mappings of R₁ into itself, with the composition property X_tu ∘ X_st = X_su, s ⩽ t ⩽ u, and with independent ‘increments’. Depending on the differentiability at 0 of the covariance function of the field of small displacements, the mapping X_st, s and t fixed, may be smooth or may be a step function mapping R₁ into a countable set of points with no limit points. (The latter kind of situation has occurred in related work of R. Arratia.) It is not known whether other behavior is possible. Some results in the countable-range case are deduced from duality results obtained for the smooth case. The case of double exponential correlation leads to a moving point process with certain spatial Markovian properties.     

Fiedler vectors with unbalanced sign patterns

Czechoslovak Mathematical Journal - In spectral bisection, a Fielder vector is used for partitioning a graph into two connected subgraphs according to its sign pattern. We investigate graphs having...     

A Note on Generic Fiedler Matrices

In this paper, we first show that a generic m×n Fiedler matrix may have 2m-n-1 kinds of factorizations which are very complicated when m is much larger than n. In this work, two special cases are examined, one is an m×n Fiedler matrix being factored as a product of (m - n) Fiedler matrices, the other is an m×(m - 2) Fiedler matrix's factorization. Then we discuss the relation among the numbers of parameters of three generic m×n, n×p and m×p Fiedler matrices, and obtain some useful results.     

Fiedler companion linearizations for rectangular matrix polynomials

The development of new classes of linearizations of square matrix polynomials that generalize the classical first and second Frobenius companion forms has attracted much attention in the last decade. Research in this area has two main goals: finding linearizations that retain whatever structure the original polynomial might possess, and improving properties that are essential for accurate numerical computation, such as eigenvalue condition numbers and backward errors. However, all recent progress on linearizations has been restricted to square matrix polynomials. Since rectangular polynomials arise in many applications, it is natural to investigate if the new classes of linearizations can be extended to rectangular polynomials. In this paper, the family of Fiedler linearizations is extended from square to rectangular matrix polynomials, and it is shown that minimal indices and bases of polynomials can be recovered from those of any linearization in this class via the same simple procedures developed previously for square polynomials. Fiedler linearizations are one of the most important classes of linearizations introduced in recent years, but their generalization to rectangular polynomials is nontrivial, and requires a completely different approach to the one used in the square case. To the best of our knowledge, this is the first class of new linearizations that has been generalized to rectangular polynomials.     

A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

Splitting trees at vertices

We present tight bounds on splitting trees into “small” subtrees.     

Facets with fewest vertices

Forv>d≧3, letm(v, d) be the smallest numberm, such that every convexd-polytope withv vertices has a facet with at mostm vertices. In this paper, bounds form(v, d) are found; in particular, for fixedd≧3, $$\frac{{r - 1}}{r} \leqslant \mathop {\lim \inf }\limits_{\upsilon \to \infty } \frac{{m(\upsilon ,d)}}{\upsilon } \leqslant \mathop {\lim \sup }\limits_{\upsilon \to \infty } \frac{{m(\upsilon ,d)}}{\upsilon } \leqslant \frac{{d - 3}}{{d - 2}}$$ , wherer=[1/3(d+1)].     

Trees through specified vertices

We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac’s theorem on the existence of Hamiltonian cycles. Namely, we prove for 1≤k≤n−2 if G is a connected graph with A⊂V(G) such that d_G(v)≥k for all v∈A, then there exists a subtree T of G such that V(T)⊃A and for all v∈A.     

The Laplacian spectral radii of unicyclic and bicyclic graphs with n vertices and k pendant vertices

In this paper, we determine graphs with the largest Laplacian spectral radius among the unicyclic and the bicyclic graphs on n vertices with k pendant vertices, respectively.