Shelling Coxeter-like complexes and sorting on trees

In their work on ‘Coxeter-like complexes’, Babson and Reiner introduced a simplicial complex ΔT associated to each tree T on n nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that ΔT is (n−b−1)-connected when the tree has b leaves. We provide a shelling for the (n−b)-skeleton of ΔT, thereby proving this conjecture. In the process, we introduce notions of weak order and inversion functions on the labellings of a tree T which imply shellability of ΔT, and we construct such inversion functions for a large enough class of trees to deduce the aforementioned conjecture and also recover the shellability of chessboard complexes Mm,n with n?2m−1. We also prove that the existence or nonexistence of an inversion function for a fixed tree governs which networks with a tree structure admit greedy sorting algorithms by inversion elimination and provide an inversion function for trees where each vertex has capacity at least its degree minus one.     

A matroid invariant via the K-theory of the Grassmannian

Let G(d,n) denote the Grassmannian of d-planes in Cn and let T be the torus n(C^∗)/diag(C^∗) which acts on G(d,n). Let x be a point of G(d,n) and let be the closure of the T-orbit through x. Then the class of the structure sheaf of in the K-theory of G(d,n) depends only on which Plücker coordinates of x are nonzero - combinatorial data known as the matroid of x. In this paper, we will define a certain map of additive groups from K^○(G(d,n)) to Z[t]. Letting gx(t) denote the image of , gx behaves nicely under the standard constructions of matroid theory, such as direct sum, two-sum, duality and series and parallel extensions. We use this invariant to prove bounds on the complexity of Kapranov's Lie complexes [M. Kapranov, Chow quotients of Grassmannians I, Adv. Soviet Math. 16 (2) (1993) 29-110], Hacking, Keel and Tevelev's very stable pairs [P. Hacking, S. Keel, E. Tevelev, Compactification of the moduli space of hyperplane arrangements, J. Algebraic Geom. 15 (2006) 657-680] and the author's tropical linear spaces when they are realizable in characteristic zero [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558]. Namely, in characteristic zero, a Lie complex or the underlying (d−1)-dimensional scheme of a very stable pair can have at most strata of dimensions n−i and d−i, respectively. This prove the author's f-vector conjecture, from [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558], in the case of a tropical linear space realizable in characteristic 0.     

Sperner labellings: A combinatorial approach

In 2002, De Loera, Peterson and Su proved the following conjecture of Atanassov: let T be a triangulation of a d-dimensional polytope P with n vertices v₁,v₂,…,vn; label the vertices of T by 1,2,…,n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if vj is on F; then there are at least n−d simplices labelled with d+1 different labels. We prove a generalisation of this theorem which refines this lower bound and which is valid for a larger class of objects.     

On the spectral radius of trees with fixed diameter

Let T_{(n, d)} be the set of trees on n vertices with diameter d. In this paper, the first spectral radii of trees in the set T_{(n, d)} (3 ? d ? n − 4) are characterized.     

The iterated Aluthge transforms of a matrix converge

Given an r×r complex matrix T, if T=U|T| is the polar decomposition of T, then, the Aluthge transform is defined byΔ(T)=|T|^1/2U|T|^1/2. Let Δn(T) denote the n-times iterated Aluthge transform of T, i.e., Δ⁰(T)=T and Δn(T)=Δ(Δn−1(T)), n∈N. We prove that the sequence {Δn(T)}_n∈N converges for every r×r matrix T. This result was conjectured by Jung, Ko and Pearcy in 2003. We also analyze the regularity of the limit function.     

L boundedness of commutator operator associated with schrödinger operators on heisenberg group

Let L = −ΔHⁿ + V be a Schrödinger operator on Heisenberg group Hⁿ, where ΔHⁿ is the sublaplacian and the nonnegative potential V belongs to the reverse Hölder class B_Q/2, where Q is the homogeneous dimension of Hⁿ  . Let T₁=(−ΔHn+V)⁻¹V,T₂=(−ΔHn+V)^−1/V₂1/2$T_1={(-\Delta H^n+V)}^{-1}V,T_2={(-\Delta H^n+V)}^{-1/2_{V}1/2}$, and T₃=(−Δ_Hn+V)^−1/2_∇Hn$T_3={(-{\Delta }_{H^n}+V)}^{-1/2}{\nabla }_{H^n}$, then we verify that [b, T_i], i = 1,2,3 are bounded on some L^p(Hⁿ), where b ∈ BMO(Hⁿ). Note that the kernel of T_i, i = 1,2,3 has no smoothness.     

Hyperelliptic Jacobians as billiard algebra of pencils of quadrics: Beyond Poncelet porisms

The thirty years old programme of Griffiths and Harris of understanding higher-dimensional analogues of Poncelet-type problems and synthetic approach to higher genera addition theorems has been settled and completed in this paper. Starting with the observation of the billiard nature of some classical constructions and configurations, we construct the billiard algebra, that is a group structure on the set T of lines simultaneously tangent to d−1 quadrics from a given confocal family in the d-dimensional Euclidean space. Using this tool, the related results of Reid, Donagi and Knörrer are further developed, realized and simplified. We derive a fundamental property of T: any two lines from this set can be obtained from each other by at most d−1 billiard reflections at some quadrics from the confocal family. We introduce two hierarchies of notions: s-skew lines in T and s-weak Poncelet trajectories, s=−1,0,…,d−2. The interrelations between billiard dynamics, linear subspaces of intersections of quadrics and hyperelliptic Jacobians developed in this paper enabled us to obtain higher-dimensional and higher-genera generalizations of several classical genus 1 results: Cayley's theorem, Weyr's theorem, Griffiths-Harris theorem and Darboux theorem.     

Irreducible circuits and Coxeter arrangements

We introduce the concept of irreducible circuits. In a vector arrangement Φ, these are configurations consisting of one vector α∈Φ in the positive linear span of an independent set Δ⊂Φ such that no proper subset of Δ has any member of Φ−Δ in its positive linear span. We show that the oriented matroid of any centrally symmetric vector arrangement is constructively determined by its irreducible circuits, and classify the irreducible circuits in root systems.     

Sets of orthogonal hypercubes of class r

A (d,n,r,t)-hypercube is an n×n×?×n (d-times) array on nr symbols such that when fixing t coordinates of the hypercube (and running across the remaining d−t coordinates) each symbol is repeated nd−r−t times. We introduce a new parameter, r, representing the class of the hypercube. When r=1, this provides the usual definition of a hypercube and when d=2 and r=t=1 these hypercubes are Latin squares. If d?2r, then the notion of orthogonality is also inherited from the usual definition of hypercubes. This work deals with constructions of class r hypercubes and presents bounds on the number of mutually orthogonal class r hypercubes. We also give constructions of sets of mutually orthogonal hypercubes when n is a prime power.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

Schrödinger operators on regular metric trees with long range potentials: Weak coupling behavior

Consider a regular d-dimensional metric tree Γ with root o. Define the Schrödinger operator −Δ−V, where V is a non-negative, symmetric potential, on Γ, with Neumann boundary conditions at o. Provided that V decays like |x|^−γ at infinity, where 1<γ?d?2, γ≠2, we will determine the weak coupling behavior of the bottom of the spectrum of −Δ−V. In other words, we will describe the asymptotic behavior of infσ(−Δ−αV) as α→0+.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

Open irredundance and maximum degree in graphs

A necessary and sufficient condition for an open irredundant set of vertices of a graph to be maximal is obtained. This result is used to show that the smallest cardinality amongst the maximal open irredundant sets in an n-vertex isolate-free graph with maximum degree Δ is at least n(3Δ−1)/(2Δ³−5Δ²+8Δ−1) for Δ≥5, n/8 for Δ=4 and 2n/11 for Δ=3. The bounds are the best possible.     

Eigenvalue distribution of second-order dynamic equations on time scales considered as fractals

Let T⊂[a,b] be a time scale with a,b∈T. In this paper we study the asymptotic distribution of eigenvalues of the following linear problem −uΔΔ=λuσ, with mixed boundary conditions αu(a)+βuΔ(a)=0=γu(ρ(b))+δuΔ(ρ(b)). It is known that there exists a sequence of simple eigenvalues k{λk}; we consider the spectral counting function , and we seek for its asymptotic expansion as a power of λ. Let d be the Minkowski (or box) dimension of T, which gives the order of growth of the number K(T,ε) of intervals of length ε needed to cover T, namely K(T,ε)≈εd. We prove an upper bound of N(λ) which involves the Minkowski dimension, N(λ,T)?Cλd/2, where C is a positive constant depending only on the Minkowski content of T (roughly speaking, its d-volume, although the Minkowski content is not a measure). We also consider certain limiting cases (d=0, infinite Minkowski content), and we show a family of self similar fractal sets where N(λ,T) admits two-side estimates.     

Extremal critically connected matroids

A connected matroid M is called a critically connected matroid if the deletion of any one element from M results in a disconnected matroid. We show that a critically connected matroid of rank n, n≥3, can have at most 2n?2 elements. We also show that a critically connected matroid of rank n on 2n?2 elements is isomorphic to the forest matroid of K₂, n?2.     

Singular continuous Floquet operator for systems with increasing gaps

Consider the Floquet operator of a time-independent quantum system, periodically perturbed by a rank one kick, acting on a separable Hilbert space: e^−iH₀Te^{−iκT|φ〉〈φ|}, where T and κ are the period and the coupling constant, respectively. Assume the spectrum of the self-adjoint operator H₀ is pure point, simple, bounded from below and the gaps between the eigenvalues (λ_n) grow like λ_n+1−λ_n∼Cn^d with d?2. Under some hypotheses on the arithmetical nature of the eigenvalues and the vector φ, cyclic for H₀, we prove the Floquet operator of the perturbed system has purely singular continuous spectrum.     

Functional calculus under the Tadmor-Ritt condition, and free interpolation by polynomials of a given degree

For Banach space operators T satisfying the Tadmor-Ritt condition ||(zI−T)⁻¹||?C|z−1|⁻¹, |z|>1, we prove that the best-possible constant C_T(n) bounding the polynomial calculus for T, ||p(T)||?C_T(n)||p||_∞, deg(p)?n, behaves (in the worst case) as as n→∞. This result is based on a new free (Carleson type) interpolation theorem for polynomials of a given degree.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.