Nerve complexes and moment-angle spaces of convex polytopes

We introduce spherical nerve complexes that are a far-reaching generalization of simplicial spheres, and consider the differential ring of simplicial complexes. We show that spherical nerve complexes form a subring of this ring, and define a homomorphism from the ring of polytopes to this subring that maps each polytope P to the nerve K _P of the cover of the boundary ∂P by facets. We develop a theory of nerve complexes and apply it to the moment-angle spaces Z _P of convex polytopes P. In the case of a polytope P with m facets, its moment-angle space Z _P is defined by the canonical embedding in the cone ℝ_≥ ^m . It is well-known that the space Z _P is homeomorphic to the polyhedral product (D ², S ¹)∂P* if the polytope P is simple. We show that the homotopy equivalence Z_P @ (D² ,S¹ )^K_P \mathcal{Z}_P \simeq (D^2 ,S^1 )^{K_P } holds in the general case. On the basis of bigraded Betti numbers of simplicial complexes, we construct a new class of combinatorial invariants of convex polytopes. These invariants take values in the ring of polynomials in two variables and are multiplicative with respect to the direct product or join of polytopes. We describe the relation between these invariants and the well-known f-polynomials of polytopes. We also present examples of convex polytopes whose flag numbers (in particular, f-polynomials) coincide, while the new invariants are different.     

Topologies on products of partially ordered sets I: Interval topologies

Given a certain construction principle assigning to each partially ordered setP some topology θ(P) onP, one may ask under what circumstances the topology θ(P) of a productP = ?_j∈J P _j of partially ordered setsP _i agrees with the product topology ?_j∈Jθ(P _i) onP. We shall discuss this question for several types ofinterval topologies (Part I), forideal topologies (Part II), and fororder topologies (Part III). Some of the results contained in this first part are listed below:

1. Let θ_i(P) denote thesegment topology. For any family of posetsP _j ?_j∈Jθ_s(P_j)=θ_s(?_j∈JP_i) iff at most a finite number of theP _j has more than one element (1.1).
2. Let θ_cs(P) denote theco-segment topology (lower topology). For any family of lower directed posetsP _j ?_j∈Jθ_cs(P_i)=θ_cs(?_j∈JP_i) iff eachP _j has a least element (1.5).
3. Let θ_i(P) denote theinterval topology. For a finite family of chainsP _j,P _j ?_j∈Jθ_i(P_i)=θ_i(?_j∈JP_i) iff for allj∈k, P _j has a greatest element orP _k has a least element (2.11).
4. Let θ_ni(P) denote thenew interval topology. For any family of posetsP _j,P _j ?_j∈Jθ_ni(P_j)=θ_ni(?_j∈JP_j) whenever the product space is ab-space (i.e. a space where the closure of any subsetY is the union of all closures of bounded subsets ofY) (3.13).

In the case oflattices, some of the results presented in this paper are well-known and have been shown earlier in the literature. However, the case of arbitraryposets often proved to be more difficult.     

Virtual Betti numbers of real algebraic varieties

We show that for all i?0 the i-th mod 2 Betti number of compact nonsingular real algebraic varieties has a unique extension to a virtual Betti numberβ_i defined for all real algebraic varieties, such that if Y is a closed subvariety of X then β_i(X)=β_i(X?Y)+β_i(Y). We show by example that there is no natural weight filtration on the $\text{Z}{}_2$-cohomology of real algebraic varieties with compact supports such that the virtual Betti numbers are the weighted Euler characteristics. To cite this article: C. McCrory, A. Parusiński, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

A unique decomposition result for HT factors with torsion free core

We prove that II₁ factors M have a unique (up to unitary conjugacy) cross-product type decomposition around “core subfactors” N⊂M satisfying the property HT of [S. Popa, On a class of type II₁ factors with Betti numbers invariants, Ann. of Math. (2) 163 (2006) 809-899] and a certain “torsion freeness” condition. In particular, this shows that isomorphism of factors of the form Lαi(Z²)?Fni, i=1,2, for Fni⊂SL(2,Z) free groups of rank ni and αj=e2πitj, tj∉Q, implies n₁=n₂.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Convex polytopes without triangular faces

LetP be a convexd-polytope without triangular 2-faces. Forj=0,…,d−1 denote byf _j(P) the number ofj-dimensional faces ofP. We prove the lower boundf _j(P)≥f _j(C _d) whereC _d is thed-cube, which has been conjectured by Y. Kupitz in 1980. We also show that for anyj equality is only attained for cubes. This result is a consequence of the far-reaching observation that such polytopes have pairs of disjoint facets. As a further application we show that there exists only one combinatorial type of such polytopes with exactly 2d+1 facets.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

The reconstruction conjecture and edge ideals

Given a simple graph G on n vertices, we prove that it is possible to reconstruct several algebraic properties of the edge ideal from the deck of G, that is, from the collection of subgraphs obtained by removing a vertex from G. These properties include the Krull dimension, the Hilbert function, and all the graded Betti numbers β_i,j where j<n. We also state many further questions that arise from our study.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Universal spaces of subdifferentials of sublinear operators ranging in the cone of bounded lower semicontinuous functions

We study Fréchet’s problem of the universal space for the subdifferentials ?P of continuous sublinear operators P: V → BC(X)_～ which are defined on separable Banach spaces V and range in the cone BC(X)_～ of bounded lower semicontinuous functions on a normal topological space X. We prove that the space of linear compact operators L ^c(? ², C(βX)) is universal in the topology of simple convergence. Here ? ² is a separable Hilbert space, and βX is the Stone-?ech compactification of X. We show that the images of subdifferentials are also subdifferentials of sublinear operators.     

Some explicit formulae in simultaneous padé approximation

Using old results on the explicit calculation of determinants, formulae are given for the coefficients of P₀(z) and P₀(z)f_i(z) ? P_i(z), where P_i(z) are polynomials of degree σ ? ρ_i (i=0,1,…,n), P₀(z)f_i(z) ? P_i(z) are power series in which the terms with z^k, 0?k?σ, vanish (i=1,2,…,n), (ρ₀,ρ₁,…,ρ_n) is an (n+1)-tuple of nonnegative integers, σ=ρ₀+ρ₁+?+ρ_n, and {f_i}ⁿ_i=1 is the set of hypergeometric functions {₁F₁(1;c_i;z)}ⁿ_i=1$\text{(c}{}_{\mathrm{i}}\text{?}\text{Z}\text{z.drule;}\text{N}\text{, c}{}_{\mathrm{i}}\text{? c}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ or {₂F₀(a_i,1;z)}ⁿ_i=1$\text{(a}{}_{\mathrm{i}}\text{?}\text{Z}\text{?}\text{N}\text{, a}{}_{\mathrm{i}}\text{? a}{}_{\mathrm{j}}\text{?}\text{Z}\text{)}$ under the condition ρ₀?ρ_i ? 1 (i=1,2,…,n).     

Regularity 3 in edge ideals associated to bipartite graphs

We focus in this paper on edge ideals associated to bipartite graphs and give a combinatorial characterization of those having regularity 3. When the regularity is strictly bigger than 3, we determine the first step i in the minimal graded free resolution where there exists a minimal generator of degree >i+3, show that at this step the highest degree of a minimal generator is i+4, and determine the corresponding graded Betti number β _i,i+4 in terms of the combinatorics of the graph. The results are then extended to the non-square-free case through polarization. We also study a family of ideals of regularity 4 that play an important role in our main result and whose graded Betti numbers can be completely described through closed combinatorial formulas.     

Bounds for the (Laplacian) spectral radius of graphs with parameter α

Let G be a simple connected graph of order n with degree sequence (d ₁, d ₂, …, d _n ). Denote ( ^α t) _i = Σ _{j: i～j} d _j ^α , ( ^α m) _i = ( ^α t) _i /d _i ^α and ( ^α N) _i = Σ _{j: i～j} ( ^α t) _j , where α is a real number. Denote by λ₁(G) and μ₁(G) the spectral radius of the adjacency matrix and the Laplacian matrix of G, respectively. In this paper, we present some upper and lower bounds of λ₁(G) and μ₁(G) in terms of ( ^α t) _i , ( ^α m) _i and ( ^α N) _i . Furthermore, we also characterize some extreme graphs which attain these upper bounds. These results theoretically improve and generalize some known results.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

A noncommutative version of the matrix inversion formula

The cofactor expression (? 1)^i+j$\text{det}\text{(I ? B)}{}_{\mathrm{<mtext>j</mtext><mtext>?</mtext><mtext>i</mtext><mtext>?</mtext>}}\text{det}\text{(I ? B)}$ for the (i, j)-entry in the inverse of a matrix (I ? B) is proved to be equal to the corresponding entry of the series Σ_m≥0B^m, by using purely combinatorial methods: circuit monoid techniques and monomial rearrangements. Moreover, the identity is shown to hold in a non-commutative formal power series algebra.     

Nonhomogeneous spectra of numbers

A simple characterization is given of those sequences of integersM_n={a_i}ⁿ_i=1for which there exist real numbers αandβ such thata_i=?iα+β?(1?i?n). In addition, for givenM_n, an open intervalI_nis computed such that α?I_nif and only ifa_i=?iα+β?(1?i?n)for suitableβ=β(α).     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Inclusion relations involving k-numerical ranges

Let W_k(A) denote the k-numerical range of an n × n matrix A. It is known that W_i(A) ? W_j(A) for 1 ? j? i? n. It this paper we derive more general inclusion relations of the form Σⁿ_iλ_iW_i(A) ? Σⁿ_iμ_iW_i(A), where λ_i, μ_i are real coefficients.     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).