On subspace arrangements of type

Let denote the subspace arrangement formed by all linear subspaces in given by equations of the form

₁x_i1=₂x_i2==_kx_ik,

where 1i₁<<i_kn and (₁,…,_k){+1,−1}^k.Some important topological properties of such a subspace arrangement depend on the topology of its intersection lattice. In a previous work on a larger class of subspace arrangements by Björner and Sagan (J. Algebraic Combin. 5 (1996) 291–314) the topology of the intersection lattice turned out to be a particularly interesting and difficult case.We prove in this paper that Pure(Π_n,k^±) is shellable, hence that Π_n,k^± is shellable for k>n/2. Moreover, we prove that unless i≡n−2 (mod k−2) or i≡n−3 (mod k−2), and that is free abelian for i≡n−2 (mod k−2). In the special case of Π_2k,k^± we determine homology completely. Our tools are generalized lexicographic shellability, as introduced in Kozlov (Ann. Combin. 1 (1997) 67–90), and a spectral sequence method for the computation of poset homology first used in Hanlon (Trans. Amer. Math. Soc. 325 (1991) 1–37).We state implications of our results on the cohomology of the complements of the considered arrangements.     

Torpid mixing of the Wang–Swendsen–Kotecký algorithm for sampling colorings

We study the problem of sampling uniformly at random from the set of k-colorings of a graph with maximum degree Δ. We focus attention on the Markov chain Monte Carlo method, particularly on a popular Markov chain for this problem, the Wang–Swendsen–Kotecký (WSK) algorithm. The second author recently proved that the WSK algorithm quickly converges to the desired distribution when k11Δ/6. We study how far these positive results can be extended in general. In this note we prove the first non-trivial results on when the WSK algorithm takes exponentially long to reach the stationary distribution and is thus called torpidly mixing. In particular, we show that the WSK algorithm is torpidly mixing on a family of bipartite graphs when 3k<Δ/(20logΔ), and on a family of planar graphs for any number of colors. We also give a family of graphs for which, despite their small chromatic number, the WSK algorithm is not ergodic when kΔ/2, provided k is larger than some absolute constant k₀.     

A Note on an Error Bound for the AOR Method

Suppose Ax = b is a system of linear equations where the matrix A is symmetric positive definite and consistently ordered. A bound for the norm of the errors _k = x– x ^k of the AOR method in terms of the norms of _k = x ^k–x ^k–1 and _k+1 = x ^k+1–x ^k and their inner product is derived.     

Explicit inverse of a tridiagonal k−Toeplitz matrix

Summary We obtain explicit formulas for the entries of the inverse of a nonsingular and irreducible tridiagonal k–Toeplitz matrix A. The proof is based on results from the theory of orthogonal polynomials and it is shown that the entries of the inverse of such a matrix are given in terms of Chebyshev polynomials of the second kind. We also compute the characteristic polynomial of A which enables us to state some conditions for the existence of A^–1. Our results also extend known results for the case when the residue mod k of the order of A is equal to 0 or k–1 (Numer. Math., 10 (1967), pp. 153–161.).The work was supported by CMUC (Centro de Matemática da Universidade de Coimbra) and by Acção Integrada Luso-Espanhola E-6/03     

<Emphasis Type="Italic">n</Emphasis>-Lie Structures That Are Generated by Wronskians

We study the (k + 1)-Lie structures, k-left commutative and homotopy (k + 1)-Lie structures with multiplication generated by Wronskians and prove that the nontrivial structures of n-Lie algebras appear only in the case of small characteristic.Original Russian Text Copyright © 2005 Dzhumadil’daev A. S.__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 759–773, July–August, 2005.     

Necessary Conditions for the Localization of the Spectrum of the Sturm-Liouville Problem on a Curve

We consider the Sturm-Liouville operator on a convex smooth curve lying in the complex plane and connecting the points 0 and 1. We prove that if the eigenvalues λ_k with large numbers are localized near a single ray, then this ray is the positive real semiaxis. Moreover, if the eigenvalues λ_k are numbered with algebraic multiplicities taken into account, then λ_k ∼ π · k as k → +∞.__________Translated from Matematicheskie Zametki, vol. 78, no. 1, 2005, pp. 72–84.Original Russian Text Copyright © 2005 by Kh. K. Ishkin.     

Generalized Neuwirth Groups and Seifert Fibered Manifolds

The topological properties of the generalized Neuwirth groups, _n^k are discussed. For examp, we demonstrate that the group, _n^k is the fundamental group of the Seifert fibered space _n^k. Moreover, discuss some other invariants and algebraic properties of the above groups.This work was supported by Polish grant (BW-5100–5–0259–9) and the Russian Foundation for Basic Research (grant number 98–01–00699).2000 Mathematics Subject Classification: 20F34, 57M05, 57M60     

Graphs with Least Eigenvalue −2: The Star Complement Technique

Let G be a connected graph with least eigenvalue –2, of multiplicity k. A star complement for –2 in G is an induced subgraph H = G – X such that |X| = k and –2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of –2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.     

Monotonicity of quadrature formulae of Gauss type and comparison theorems for monosplines

Summary This paper deals with quadrature formulae of Gauss type corresponding to subspaces of spline functionsS _{m–1, k} of degreem–1 withk fixed knots. We shall show monotonicity of the quadrature formulae for functions which are contained in the so-called convexity cone ofS _m–1,k Moreover, we apply these results to monosplines and establish comparison theorems for these splines.     

Toughness and the existence ofk-factors. II

In a paper with the same title [3], we proved Chvátal's conjecture thatk-tough graphs havek-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose|V(G)| k + 1,k |V(G)| even, and|S| k w(G – S) – 7/8k ifw(G – S) 2, wherew(G – S) is the number of connected components ofG – S. ThenG has ak-factor.     

Exact k-Wise Intersection Theorems

A typical problem in extremal combinatorics is the following. Given a large number n and a set L, find the maximum cardinality of a family of subsets of a ground set of n elements such that the intersection of any two subsets has cardinality in L. We investigate the generalization of this problem, where intersections of more than 2 subsets are considered. In particular, we prove that when k–1 is a power of 2, the size of the extremal k-wise oddtown family is (k–1)(n– 2log₂(k–1)). Tight bounds are also found in several other basic cases.Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH ZürichResearch supported in part by NSF grant DMS-0200357, by an NSF CAREER award and by an Alfred P. Sloan fellowship. webpage: http://www.math.ucsd.edu/vanvu/     

Perfect matchings in regular bipartite graphs

P. Hall, [2], gave necessary and sufficient conditions for a bipartite graph to have a perfect matching. Koning, [3], proved that such a graph can be decomposed intok edge-disjoint perfect matchings if and only if it isk-regular. It immediately follows that in ak-regular bipartite graphG, the deletion of any setS of at mostk – 1 edges leaves intact one of those perfect matchings. However, it is not known what happens if we delete more thank – 1 edges. In this paper we give sufficient conditions so that by deleting a setS ofk + r edgesr 0, stillG – S has a perfect matching. Furthermore we prove that our result, in some sense, is best possible.     

Some Asymptotic Formulae for q-Shifted Factorials

The q-shifted factorial defined by (a : q^k) _n = (1 – a) (1 – aq^k)(1 – aq^2k)... (1 – aq^{(n – 1)k}) appears in the terms of basic hypergeometric series. Complete asymptotic expansions as q 1 of some q-shifted factorials are given in terms of polylogarithms and Bernoulli polynomials.     

Linking (n − 2)-dimensional panels inn-space I: (k − 1,k)-graphs and (k − 1,k)-frames

A (k – 1,k)-graph is a multi-graph satisfyinge (k – 1)v – k for every non-empty subset ofe edges onv vertices, with equality whene = |E(G)|. A (k – 1,k)-frame is a structure generalizing an (n – 2, 2)-framework inn-space, a structure consisting of a set of (n – 2)-dimensional bodies inn-space and a set of rigid bars each joining a pair of bodies using ball joints. We prove that a graph is the graph of a minimally rigid (with respect to edges) (k – 1,k)-frame if and only if it is a (k – 1,k)-graph. Rigidity here means infinitesimal rigidity or equivalently statical rigidity.     

Elliptic semiplanes and group divisible designs with orthogonal resolutions

In this paper we prove that there exists an elliptic semiplaneS(v, k, m) withk –m 2 if and only if there exists a group divisible design GDD _k ((k –m)(k – 1);k –m; 0, 1) withm pairwise orthogonal resolutions. As an example of this theorem, we construct an elliptic semiplaneW(45, 7, 3) and show thatW is isomorphic to the elliptic semiplaneS(45, 7, 3) given by R. D. Baker.     

Some remarks on (k−1)-critical subgraphs ofk-critical graphs

A graphG is said to bek-critical if it has chromatic numberk, but every proper subgraph ofG has a (k–1)-coloring. Gallai asked whether every largek-critical graph contains many (k–1)-critical subgraphs. We provide some information concerning this question and some related questions.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

On the poisedness of Bojanov–Xu interpolation

In this paper, we consider the bivariate Hermite interpolation introduced by Bojanov and Xu [SIAM J. Numer. Anal. 39(5) (2002) 1780–1793]. The nodes of the interpolation with Π_2k-δ, where δ=0 or 1, are the intersection points of 2k+1 distinct rays from the origin with a multiset of k+1-δ concentric circles. Parameters are the values and successive radial derivatives, whenever the corresponding circle is multiple. The poisedness of this interpolation was proved only for the set of equidistant rays [Bojanov and Xu, 2002] and its counterparts with other conic sections [Hakopian and Ismail, East J. Approx. 9 (2003) 251–267]. We show that the poisedness of this (k+1-δ)(2k+1) dimensional Hermite interpolation problem is equivalent to the poisedness of certain 2k+1 dimensional Lagrange interpolation problems. Then the poisedness of Bojanov–Xu interpolation for a wide family of sets of rays satisfying some simple conditions is established. Our results hold also with above circles replaced by ellipses, hyperbolas, and pairs of parallel lines.Next a conjecture [Hakopian and Ismail, J. Approx. Theory 116 (2002) 76–99] concerning a poisedness relation between the Bojanov–Xu interpolation, with set of rays symmetric about x-axis, and certain univariate lacunary interpolations is established. At the end the poisedness for a wide class of lacunary interpolations is obtained.     

Quotient algebras of Stanley-Reisner rings and local cohomology

We study certain subcomplexes Δ′ of an arbitrary simplicial complex Δ such that H_mⁱ(k[Δ])-H_mⁱ(k[Δ′]) for any 0i<dim(k[Δ′]). Here, H_mⁱ(k[Δ]) is the ith local cohomology module of the Stanley-Reisner ring k[Δ] of Δ over a field k. Our technique is an elegant approach to one of the most generalized versions of the rank selection theorems of J. Munkres (1984, Michigan Math. J.31, 113–128, Theorem 6.4) and R. Stanley (1979, Trans. Amer. Math. Soc.249, 139–157, Theorem 4.3).     

Solution and stability of generalized mixed type cubic, quadratic and additive functional equation in quasi-Banach spaces

In this paper, we achieve the general solution and the generalized Hyers–Ulam–Rassias stability of the following functional equation

f(x+ky)+f(x−ky)=k²f(x+y)+k²f(x−y)+2(1−k²)f(x)