A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement.     

Relative widths of smooth functions determined by linear differential operator

Let W and V be centrally symmetric sets in a normed space X. The relative Kolmogorov n-width of W relative to V in X is defined by

     

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E), a family W of sets W⊆V of vertices (areas), and a requirement function r:W→Z⁺ (where Z⁺ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1 for each W∈W, and polynomially solvable in the uniform case of r(W)=r?2 for each W∈W. In this paper, we show that the problem can be solved in time, even if r(W)?2 holds for each W∈W, where n=|V|, m=|{{u,v}|(u,v)∈E}|, p=|W|, and r^*=max{r(W)∣W∈W}.     

Moments of Two-Variable Functions and the Uniqueness of Graph Limits

For a symmetric bounded measurable function W on [0, 1]² and a simple graph F, the homomorphism density $t(F,W) = \int _{[0,1]^{V (F)}} \prod_ {i j\in E(F)} W(x_i, x_j)dx .$ can be thought of as a “moment” of W. We prove that every such function is determined by its moments up to a measure preserving transformation of the variables. The main motivation for this result comes from the theory of convergent graph sequences. A sequence (G _n ) of dense graphs is said to be convergent if the probability, t(F, G _n ), that a random map from V(F) into V(G _n ) is a homomorphism converges for every simple graph F. The limiting density can be expressed as t(F, W) for a symmetric bounded measurable function W on [0, 1]². Our results imply in particular that the limit of a convergent graph sequence is unique up to measure preserving transformation.     

Asymptotic distribution of the OLS estimator for a mixed spatial model

We find the asymptotic distribution of the OLS estimator of the parameters β and ρ in the mixed spatial model with exogenous regressors Y_n=X_nβ+ρW_nY_n+V_n. The exogenous regressors may be bounded or growing, like polynomial trends. The assumption about the spatial matrix W_n is appropriate for the situation when each economic agent is influenced by many others. The error term is a short-memory linear process. The key finding is that in general the asymptotic distribution contains both linear and quadratic forms in standard normal variables and is not normal.     

The constrained bilinear form and the C-numerical range

Let V be an n-dimentional unitary space with inner product (·,·) and S the set {x∈V:(x, x)=1}. For any A∈Hom(V, V) and $\text{q∈}\text{C}$ with ∣q∣?1, we define

$\text{W(A:q)={(Ax, y):x, y∈S, (x, y)=q}}$

. If q=1, then W(A:q) is just the classical numerical range {(Ax, x):x∈S}, the convexity of which is well known. Another generalization of the numerical range is the C-numerical range, which is defined to be the set

$\text{W}{}_{\mathrm{C}}\text{(A)={}\text{tr}\text{(CU}{}^1\text{AU):U}\text{unitary}\text{}}$

where C∈Hom(V, V). In this note, we prove that W(A:q) is always convex and that W_C(A) is convex for all A if rank C=1 or n=2.     

Geometric tools to determine the hyperbolicity of limit cycles

In this paper we present a new method to study limit cycles' hyperbolicity. The main tool is the function ν=([V,W]∧V)/(V∧W), where V is the vector field under investigation and W a transversal one. Our approach gives a high degree of freedom for choosing operators to study the stability. It is related to the divergence test, but provides more information on the system's dynamics. We extend some previous results on hyperbolicity and apply our results to get limit cycles' uniqueness. Liénard systems and conservative + dissipative systems are considered among the applications.     

Toppling kings in multipartite tournaments by introducing new kings

Let and be two n-tuples of nonnegative integers. An all-4-kings n-partite tournament T(V₁,V₂,…V_n) is said to have a -property if there exists an n-partite tournament T₁(W₁,W₂,…,W_n) such that for each i∈{1,…,n}:

(1)

V_i⊆W_i;

(2)

exactly t_i 4-kings of V_i are not 4-kings in T₁;

(3)

exactly c_i 4-kings of W_i are not vertices of V_i.

We describe all pairs such that there exists an n-partite tournament having -property.     

Stabilizing Heegaard splittings of toroidal 3-manifolds

Let T be a separating incompressible torus in a 3-manifold M. Assuming that a genus g Heegaard splitting VS_∪W can be positioned nicely with respect to T (e.g., VS_∪W is strongly irreducible), we obtain an upper bound on the number of stabi-lizations required for VS_∪W to become isotopic to a Heegaard splitting which is an amalgamation along T. In particular, if T is a canonical torus in the JSJ decomposition of M, then the number of necessary stabilizations is at most 4g−4. As a corollary, this establishes an upper bound on the number of stabilizations required for VS_∪W and any Heegaard splitting obtained by a Dehn twist of VS_∪W along T to become isotopic.     

First Fundamental Theorem for Covariants of Classical Groups

Let U(G) be a maximal unipotent subgroup of one of the classical groups G=GL(V), O(V), Sp(V). Let W be a direct sum of copies of V and its dual V*. For the natural action U(G) : W, we describe a minimal system of homogeneous generators for the algebra of U(G)-invariant regular functions on W. For G=O(V), Sp(V), this result is connected with a construction for the irreducible representations of G due to H. Weyl.     

Linear independence of the principal solutions at ∞ and −∞ for formally self-adjoint differential systems

Linear independence of the principal solutions at ∞ and ?∞ for identically normal, formally self-adjoint differential systems $\text{U′ = AU + BV, V′ = CU ? A}{}^1\text{V}$, with B ? 0, which are disconjugate on (?∞, ∞), is characterized by the condition W_?∞ < W_∞ on (?∞, ∞), where W_∞, [W_?∞], is the distinguished solution of the associated Riccati equation at ∞, [?∞]. A comparison type theorem between the above system and certain Sturmian majorants gives order relations for the corresponding distinguished solutions. The work is motivated by that of Anderson and Lazer for self-adjoint scalar equations of order 2n. For certain types of such equations, the results allow a direct sum decomposition into two n dimensional families, one whose solutions are in L₂(?∞, 0] and the other whose solutions are in L₂[0, ∞).     

Periodic solutions of symmetric autonomous Newtonian systems

In this paper we show the existence and bifurcation of T-periodic solutions of a special form for an autonomous Newtonian system with symmetry. If the phase-space R2n is equipped with the structure of an orthogonal representation (W,ρW) and the potential is invariant, then for every such a solution the set of indices of nonvanishing Fourier coefficients is finite and depends on W only. If the potential V depends on the squares of complex coordinates, then for every such a solution T is the minimal period.     

Homogeneous polynomials as Lyapunov functions in the stability research of solutions of difference equations

The linear autonomous system of difference equations x(n+1)=Ax(n) is considered, where is a real nonsingular k×k matrix. In this paper it has been proved that if W(x) is any homogeneous polynomial of m-th degree in x, then there exists a unique homogeneous polynomial V(x) of m-th degree such that ΔV=V(Ax)-V(x)=W(x) if and only if where are the eigenvalues of the matrix A. The theorem on the instability has also been proved.     

Obstructions to embedding disks II (a proof of a conjecture of Hudson)

For a manifold W of dimension m with boundary ?W, the vanishing of certain intersection and self-intersection invariants is a necessary condition to embedding n-disks. For (W, ?W) 2n ?m connected, it is also sufficient.     

On the decoupling of finite singularities from the question of asymptotic completeness in two body quantum systems

Let V be a multiplication operator, whose negative part, V?(V? ? 0) obeys ? Δ + (1 + ?)V? ? ?c for some ?, c > 0. Let W = V_χ where χ is the characteristic function of the exterior of a ball. Our main result asserts that the scattering for ? Δ + V is complete if and only if that for ? Δ + W is complete. Our technical estimates exploit Wiener integrals and the Feynman-Kac formula. We also make an application to acoustical scattering.     

Banded matrices with banded inverses,II: Locally finite decomposition of spline spaces

Given two function spacesV ₀,V ₁ with compactly supported basis functionsC _i, F_i, i∈Z, respectively, such thatC _i can be written as a finite linear combination of theF _i's, we study the problem of decomposingV ₁ into a direct sum ofV ₀ and some subspaceW ofV ₁ in such a way thatW is spanned by compactly supported functions and that eachF _i can be written as a finite linear combination of the basis functions inV ₀ andW. The problem of finding such locally finite decompositions is shown to be equivalent to solving certain matrix equations involving two-slanted matrices. These relations may be reinterpreted in terms of banded matrices possessing banded inverses. Our approach to solving the matrix equations is based on factorization techniques which work under certain conditions on minors. In particular, we apply these results to univariate splines with arbitrary knot sequences.     

Eigenfunctions of expected value operators in the Wishart distribution,II

Let V = (v_ij) denote the k × k symmetric scatter matrix following the Wishart distribution W(k, n, Σ). The problem posed is to characterize the eigenfunctions of the expectation operators of the Wishart distribution, i.e., those scalar-valued functions f(V) such that (E_nf)(V) = λ_n,kf(V). A finite sequence of polynomial eigenspaces, EP spaces, exists whose direct sum is the space of all homogeneous polynomials. These EP subspaces are invariant and irreducible under the action of the congruence transformation V → T′VT. Each of these EP subspaces contains an orthogonally invariant subspace of dimension one. The number of EP subspaces is determined and eigenvalues are computed. Bi-linear expansions of $\text{|I + VA|}{}^{\mathrm{<mtext>?n</mtext><mtext>2</mtext>}}$ and (tr VA)^r into eigenfunctions are given. When f(V) is an EP polynomial, then f(V^?1) is an EP function. These EP subspaces are identical to the more abstractly defined polynomial subspaces studied by James.