The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

Homotopy of Non-Modular Partitions and the Whitehouse Module

We present a class of subposets of the partition lattice _n with the following property: The order complex is homotopy equivalent to the order complex of _n – 1, and the S _n -module structure of the homology coincides with a recently discovered lifting of the S _n – 1-action on the homology of _n – 1. This is the Whitehouse representation on Robinson's space of fully-grown trees, and has also appeared in work of Getzler and Kapranov, Mathieu, Hanlon and Stanley, and Babson et al.One example is the subposet P _n ⁿ – 1 of the lattice of set partitions _n , obtained by removing all elements with a unique nontrivial block. More generally, for 2 k n – 1, let Q _n ^k denote the subposet of the partition lattice _n obtained by removing all elements with a unique nontrivial block of size equal to k, and let P _n ^k = _{i = 2} ^k Q _n ⁱ . We show that P _n ^k is Cohen-Macaulay, and that P _n ^k and Q _n ^k are both homotopy equivalent to a wedge of spheres of dimension (n – 4), with Betti number . The posets Q _n ^k are neither shellable nor Cohen-Macaulay. We show that the S _n -module structure of the homology generalises the Whitehouse module in a simple way.We also present a short proof of the well-known result that rank-selection in a poset preserves the Cohen-Macaulay property.     

Equational theory of idempotent algebras

A finitely based equational class of idempotent algebras of type <m, n>,m, n≥2, is two-based. More generally, any finitely based equational class of idempotent algebras of type <m ₁, ..., m_k> withm _i≥2 andk≥2 isk-based.     

Transformations of polar Grassmannians preserving certain intersecting relations

Let Π be a polar space of rank n≥3. Denote by \({\mathcal{G}}_{k}(\varPi)\) the polar Grassmannian formed by singular subspaces of Π whose projective dimension is equal to k. Suppose that k is an integer not greater than n?2 and consider the relation \({\mathfrak{R}}_{i,j}\) , 0≤i≤j≤k+1, formed by all pairs \((X,Y)\in{\mathcal{G}}_{k}(\varPi)\times{\mathcal{G}}_{k}(\varPi)\) such that dim _p (X ^⊥∩Y)=k?i and dim _p (X∩Y)=k?j (X ^⊥ consists of all points of Π collinear to every point of X). We show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{1,1}\) is induced by an automorphism of Π, except the case where Π is a polar space of type D _n with lines containing precisely three points. If k=n?t?1, where t is an integer satisfying n≥2t≥4, we show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{0,t}\) is induced by an automorphism of Π.     

Complexity Estimates for the Schmüdgen Positivstellensatz

LetKbe a closed basic set inRⁿgiven by the polynomial inequalities φ₁≥ 0, . . . , φ_m≥ 0 and let Σ be the semiring generated by the φ_kand the squares inR[x₁, . . . ,x_n]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iff∈R⁺+ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0⁺, in any representation off + das an element of Σ in terms of the φ_k, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd^−1/2≤N(d) ≤Cd^−1/2log (1/d).     

The Pre-WDVV Ring of Physics and its Topology

We show how a simplicial complex arising from the WDVV (Witten-Dijkgraaf-Verlinde-Verlinde) equations of string theory is the Whitehouse complex. Using discrete Morse theory, we give an elementary proof that the Whitehouse complex Δ_n is homotopy equivalent to a wedge of (n−2)! spheres of dimension n−4. We also verify the Cohen-Macaulay property. Additionally, recurrences are given for the face enumeration of the complex and the Hilbert series of the associated pre-WDVV ring. 2000 Mathematics Subject Classification: Primary—13F55, Secondary—05E99, 55P15     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

Vertex-, edge-, and total-colorings of Sierpiński-like graphs

Vertex-colorings, edge-colorings and total-colorings of the Sierpiński gasket graphs S_n, the Sierpiński graphs S(n,k), graphs S⁺(n,k), and graphs S⁺⁺(n,k) are considered. In particular, χ^″(S_n), χ^′(S(n,k)), χ(S⁺(n,k)), χ(S⁺⁺(n,k)), χ^′(S⁺(n,k)), and χ^′(S⁺⁺(n,k)) are determined.     

Boolean formulae, hypergraphs and combinatorial topology

With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.     

Paths of homomorphisms from stable Kneser graphs

We denote by SG _n,k the stable Kneser graph (Schrijver graph) of stable n-subsets of a set of cardinality 2n+k. For k≡3 (mod 4) and n≥2 we show that there is a component of the χ-colouring graph of SG _n,k which is invariant under the action of the automorphism group of SG _n,k . We derive that there is a graph G with χ(G)=χ(SG _n,k ) such that the complex Hom(SG _n,k ,G) is non-empty and connected. In particular, for k≡3 (mod 4) and n≥2 the graph SG _n,k is not a test graph.     

Zeros of analytic functions and norms of inverse matrices

Letk _n be the smallest constant such that for anyn-dimensional normed spaceX and any invertible linear operatorT ∈L(X) we have $|\det (T)| \cdot ||T^{ - 1} || \le k_n |||T|^{n - 1} $ . LetA ₊ be the Banach space of all analytic functionsf(z)=Σ _k≥0 a _kz^k on the unit diskD with absolutely convergent Taylor series, and let ‖f‖A ₊=σ _k≥0 |ακ|; define ? _n on $\overline D ^n $ by $ \begin{array}{l} \varphi _n \left( {\lambda _1 ,...,\lambda _n } \right) \\ = inf\left\{ {\left\| f \right\|_{A + } - \left| {f\left( 0 \right)} \right|; f\left( z \right) = g\left( z \right)\prod\limits_{i = 1}^n {\left( {\lambda _1 - z} \right), } g \in A_ + , g\left( 0 \right) = 1 } \right\} \\ \end{array} $ . We show thatk _n=sup {? _n(λ₁,…, λ _n ); (λ₁,…, λ _n )∈ $\overline D ^n $ }. Moreover, ifS is the left shift operator on the space ?∞:S(x ₀,x ₁, …,x _p, …)=(x ₁,…,x _p,…) and if J_n(S) denotes the set of allS-invariantn-dimensional subspaces of ?∞ on whichS is invertible, we have $k_n = \sup \{ |\det (S|_E )|||(S|_E )^{ - 1} ||E \in J_n (S)\} $ . J. J. Schäffer (1970) proved thatk _n≤√en and conjectured thatk _n=2, forn≥2. In factk ₃>2 and using the preceding results, we show that, up to a logarithmic factor,k _n is of the order of √n whenn→+∞.     

Some irreducibility and indecomposability results for truncated binomial polynomials of small degree

In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every n≥k+2. Under the same assumption n≥k+2, we also show that the polynomial P _n,k cannot be expressed as a composition P _n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,n≥k+1 the roots of the polynomial P _m,k cannot be obtained from the roots of P _n,k , where m≠n, by a linear map.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Sampling distribution of Gini's index of diversity

In the case of a multinomial distribution Π₁(1-Π₁)+Π₂(1-Π₂)+…+ Π_k(1-Π_k) is at times referred to as Gini's index of diversity. In this paper, we present the distributional properties of the statistic

, based on samples of size n for a homogeneous multinomial distribution. For 2≤n≤ 12 and 2≤k≤12, we give a short table of the pdf, cdf, and the moments of D. For large values of n, we mention some results for the asymptotic distribution of D for the general multinomial distribution.     

Homotopy Type of Complexes of Graph Homomorphisms between Cycles

In this paper we study the homotopy type of Hom(C_m,C_n), where C_k is the cyclic graph with k vertices. We enumerate connected components of Hom(C_m,C_n) and show that each such component is either homeomorphic to a point or homotopy equivalent to S¹. Moreover, we prove that Hom(C_m,L_n) is either empty or is homotopy equivalent to the union of two points, where L_n is an n-string, i.e., a tree with n vertices and no branching points.     

Consecutive integers in high-multiplicity sumsets

Sharpening (a particular case of) a result of Szemerédi and Vu [4] and extending earlier results of Sárközy [3] and ourselves [2], we find, subject to some technical restrictions, a sharp threshold for the number of integer sets needed for their sumset to contain a block of consecutive integers, whose length is comparable with the lengths of the set summands.A corollary of our main result is as follows. Let k,l≥1 and n≥3 be integers, and suppose that A ₁,…,A _k ?[0,l] are integer sets of size at least n, none of which is contained in an arithmetic progression with difference greater than 1. If k≥2?(l?1)/(n?2)?, then the sumset A ₁+???+A _k contains a block of at least k(n?1)+1 consecutive integers.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.     

Permutation functions and (n,m)-commutativity of semigroups

By [4], a semigroupS is called an (n, m)-commutative semigroup (n, m ∈ ?⁺, the set of all positive integers) if $$x_1 x_2 \cdot \cdot \cdot x_n y_1 y_2 \cdot \cdot \cdot y_m = y_1 y_2 \cdot \cdot \cdot y_m x_1 x_2 \cdot \cdot \cdot x_n $$ holds for allx ₁,...,x _n ,y ₁,...,y _m ∈S It is evident that ifS is an (n, m)-commutative semigroup then it is (n′,m′)-commutative for alln′≥n andm′≥m. In this paper, for an arbitrary semigroupS, we determine all pairs (n, m) of positive integersn andm for which the semigroupS is (n, m)-commutative. In our investigation a special type of function mapping ?⁺ into itself plays an important role. These functions which are defined and discussed here will be called permutation functions.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.