Bitableau bases for Garsia-Haiman modules of hollow type

Garsia-Haiman modules C[Xn,Yn]/Iγ are quotient rings in the variables Xn={x₁,x₂,…,xn} and Yn={y₁,y₂,…,yn} that generalize the quotient ring C[Xn]/I, where I is the ideal generated by the elementary symmetric polynomials ej(Xn) for 1?j?n. A bitableau basis for the Garsia-Haiman modules of hollow type is constructed. Applications of this basis to representation theory and other related polynomial spaces are considered.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Combinatorics of sequential dynamical systems

In this paper we study sequential dynamical systems (SDS) over words. Our main result is the classification of SDS over words for fixed graph Y and family of local maps (F_vi) by means of a novel notion of SDS equivalence. This equivalence arises from a natural group action on acyclic orientations. An SDS consists of: (a) a graph Y, (b) a family of vertex indexed Y-local maps F_vi:Kⁿ→Kⁿ, where K is a finite field and (c) a word w, i.e. a family (w₁,…,w_k), where w_j is a Y-vertex. A map F_vi(x_v1,…,x_vn) is called Y-local iff it fixes all variables x_vj≠x_vi and depends exclusively on the variables x_vj, for v_j∈B₁(v_i). The SDS-map is obtained by composing the local maps F_vi according to the word w: . Mutual dependencies of the local maps arising from their sequential application are expressed in the graph G(w,Y) having vertex set {1,…,k} (the indices of the word w) and in which r,s are adjacent iff w_s,w_r are adjacent in Y. We prove a bijection from equivalence classes of SDS-words into equivalence classes of acyclic orientations of G(w,Y). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.     

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.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) having the ath power (x_i,x_j)^a of the greatest common divisor of x_i and x_j as its i,j-entry divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

A random intersection digraph: Indegree and outdegree distributions

Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc i→j is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤i≤n, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m→∞.     

Quantum effects, sequential independence and majorization

A quantum effect is a positive Hilbert space contraction operator. If {E_i}, 1?i?n, are n quantum effects (defined on some Hilbert space H), then their sequential product is the operator . It is proved that the quantum effects {E_i}, 1?i?n, are sequentially independent if and only if for every permutation r₁r₂…r_n of the set S_n={1,2,…,n}. The sequential independence of the effects E_i, 1?i?n, implies E_noE_n-1o…oE_j+1oE_jo…oE₁=(E_noE_n-1o…E_j+1)oE_jo…oE₁ for every 1?j?n. It is proved that if there exists an effect E_j, 1?j?n, such that E_j?(E_noE_n-1o…E_j+1)oE_jo…oE₁, then the effects {E_i} are sequentially independent and satisfy .     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.     

Δ-Monotone arrangements of real numbers

Given a set of M × N real numbers, can these always be labeled as x_i,j; i = 1,…, M; j = 1,…, N; such that x_i+1,j+1 ? x_i+1,j ? x_i,j+1 + x_ij ≥ 0, for every (i, j) where 1 ≤ i ≤ M ? 1, 1 ≤ j ≤ N ? 1? For M = N = 3, or smaller values of M, N it is shown that there is a “uniform” rule. However, for max(M, N) > 3 and min(M, N) ≥ 3, it is proved that no uniform rule can be given. For M = 3, N = 4 a way of labeling is demonstrated. For general M, N the problem is still open although, for a special case where all the numbers are 0's and 1's, a solution is given.     

On certain spaces of lattice diagram determinants

The aim of this work is to study some lattice diagram determinants Δ_L(X,Y) as defined in (Adv. Math. 142 (1999) 244) and to extend results of Aval et al. (J. Combin. Theory Ser. A, to appear). We recall that M_L denotes the space of all partial derivatives of Δ_L. In this paper, we want to study the space M_i,j^k(X,Y) which is defined as the sum of M_L spaces where the lattice diagrams L are obtained by removing k cells from a given partition, these cells being in the “shadow” of a given cell (i,j) in a fixed Ferrers diagram. We obtain an upper bound for the dimension of the resulting space M_i,j^k(X,Y), that we conjecture to be optimal. This dimension is a multiple of n! and thus we obtain a generalization of the n! conjecture. Moreover, these upper bounds associated to nice properties of some special symmetric differential operators (the “shift” operators) allow us to construct explicit bases in the case of one set of variables, i.e. for the subspace M_i,j^k(X) consisting of elements of 0 Y-degree.     

Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum

We investigate simultaneous solutions of the matrix Sylvester equations A_iX-XB_i=C_i,i=1,2,…,k, where {A₁,…,A_k} and {B₁,…,B_k} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C₁,…,C_k} if and only if the joint spectra σ(A₁,…,A_k) and σ(B₁,…,B_k) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations.     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Boolean invertible matrices identified from two permutations and their corresponding Haar-type matrices

We construct a class R_m of m×m boolean invertible matrices whose elements satisfy the following property: when we perform the Hadamard product operation R_i⊙R_j on the set of row vectors {R₁,…,R_m} of an element R∈R_m we produce either the row R_max{i,j} or the zero row. In this paper, we prove that every matrix R∈R_m is uniquely determined by a pair of permutations of the set {1,…,m}. As a by-product of this result we identify Haar-type matrices from a pair of permutations as well, because these matrices emerge from the Gram-Schmidt orthonormalization process of the set of row vectors of R matrices belonging in a certain subclass R₀⊂R_m.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Small deviations of the maximal element of a sequence of weighted independent random variables

Consider a sequence {X _i } of independent copies of a nonnegative random variable X and let M = sup _{j ≥ 1}λ _j X _j , where {λ _j } is a nonincreasing sequence of positive numbers for which P(M < ∞) = 1. The asymptotic behavior of -logP(M < r) as r → 0 is studied.     

Asymptotic Behavior of the Maximum of Sums of I.I.D. Random Variables along Monotone Blocks

Let {X_i, Y_i}_i=1,2,... be an i.i.d. sequence of bivariate random vectors with P(Y₁ = y) = 0 for all y. Put M_n(j) = max_0≤k≤n-j (X_k+1 + ... X_k+j)I_k,j, where I_k,k+j = I{Y_k+1 < ⋯ < Y_k+j} denotes the indicator function for the event in brackets, 1 ≤ j ≤ n. Let L_n be the largest index l ≤ n for which I_k,k+l = 1 for some k = 0, 1, ..., n - l. The strong law of large numbers for “the maximal gain over the longest increasing runs,” i.e., for M_n(L_n) has been recently derived for the case where X₁ has a finite moment of order 3 + ε, ε > 0. Assuming that X₁ has a finite mean, we prove for any a = 0, 1, ..., that the s.l.l.n. for M(L_n - a) is equivalent to EX ₁ ^3+a I{X₁ > 0} < ∞. We derive also some new results for the a.s. asymptotics of L_n. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 311, 2004, pp. 179–189.     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

The mixing advantage for bounded random variables

Corresponding to n independent non-negative random variables X₁,…,X_n concentrated on a bounded interval set are values M₁,…,M_n, where each M_i is the expected value of the maximum of n independent copies of X_i. We obtain a sharp upper bound for the expected value of the maximum of X₁,…,X_n in terms of M₁,…,M_n. This inequality is sharp. A similar result is demonstrated for minima.