A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y₁,…,Y_p} of subsets of {1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M) of ordered pairs (i,j) satisfying i≠j and Y_i⊆Y_j is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.     

Oberwolfach rectangular table negotiation problem

We completely solve certain case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Let H(k,3) be a bipartite graph with bipartition X={x₁,x₂,…,x_k},Y={y₁,y₂,…,y_k} and edges x₁y₁,x₁y₂,x_ky_k−1,x_ky_k, and x_iy_i−1,x_iy_i,x_iy_i+1 for i=2,3,…,k−1. We completely characterize all complete bipartite graphs K_n,n that can be factorized into factors isomorphic to G=mH(k,3), where k is odd and mH(k,3) is the graph consisting of m disjoint copies of H(k,3).     

Bitableaux Bases for the Diagonally Invariant Polynomial Quotient Rings

LetR=Q[x₁, x₂, …, x_n,y₁, y₂, …, y_n,z₁, …, z_n,w₁, …, w_n], letR^S_n={P∈R:σP=P∀σ∈S_n} and letμandνbe hook shape partitions ofn. WithΔ_μ(X, Y) andΔ_ν(Z, W) being appropriately defined determinants, ∂_xibeing the partial derivative operator with respect tox_iandP(∂)=P(∂_x1, …, ∂_xn, ∂_y1, …, ∂_wn), define _{μ, ν}={P∈R^S_n:P(∂)Δ_μ(X, Y)Δ_ν(Z, W)=0}. A basis is constructed for the polynomial quotient ringR^S_n/_{μ, ν}that is indexed by pairs of standard tableaux. The Hilbert series ofR^S_n/_{μ, ν}is related to the Macdonaldq, t-Kostka coefficients.     

Conditional ordering of order statistics

For any positive integers m and n, let X₁,X₂,…,X_m∨n be independent random variables with possibly nonidentical distributions. Let X_1:n≤X_2:n≤?≤X_n:n be order statistics of random variables X₁,X₂,…,X_n, and let X_1:m≤X_2:m≤?≤X_m:m be order statistics of random variables X₁,X₂,…,X_m. It is shown that (X_j:n,X_j+1:n,…,X_n:n) given X_i:m>y for j−i≥max{n−m,0}, and (X_1:n,X_2:n,…,X_j:n) given X_i:m≤y for j−i≤min{n−m,0} are all increasing in y with respect to the usual multivariate stochastic order. We thus extend the main results in Dubhashi and Häggström (2008) [1] and Hu and Chen (2008) [2].     

Variation of parameters and solutions of composite products of linear differential equations

Given a basis of solutions to k ordinary linear differential equations ?j[y]=0(j=1,2,…,k), we show how Green's functions can be used to construct a basis of solutions to the homogeneous differential equation ?[y]=0, where ? is the composite product ?=?₁?₂…?k. The construction of these solutions is elementary and classical. In particular, we consider the special case when . Remarkably, in this case, if {y₁,y₂,…,yn} is a basis of ?₁[y]=0, then our method produces a basis of for any k∈N. We illustrate our results with several classical differential equations and their special function solutions.     

Representation of group elements as subsequence sums

Let G be a finite (additive written) abelian group of order n. Let w₁,…,w_n be integers coprime to n such that w₁+w₂+?+w_n≡0 (mod n). Let I be a set of cardinality 2n-1 and let ξ={x_i:i∈I} be a sequence of elements of G. Suppose that for every subgroup H of G and every a∈G, ξ contains at most terms in a+H.Then, for every y∈G, there is a subsequence {y₁,…,y_n} of ξ such that y=w₁y₁+?+w_ny_n.Our result implies some known generalizations of the Erd?s-Ginzburg-Ziv Theorem.     

Relations between the Clausen and Kazhdan-Lusztig representations of the symmetric group

We use Kazhdan-Lusztig polynomials and subspaces of the polynomial ring C[x_1,1,…,x_n,n] to give a new construction of the Kazhdan-Lusztig representations of S_n. This construction produces exactly the same modules as those which Clausen constructed using a different basis in [M. Clausen, Multivariate polynomials, standard tableaux, and representations of symmetric groups, J. Symbolic Comput. (11), 5-6 (1991) 483-522. Invariant-theoretic algorithms in geometry (Minneapolis, MN, 1987)], and does not employ the Kazhdan-Lusztig preorders. We show that the two resulting matrix representations are related by a unitriangular transition matrix. This provides a C[x_1,1,…,x_n,n]-analog of results due to Garsia and McLarnan, and McDonough and Pallikaros, who related the Kazhdan-Lusztig representations to Young’s natural representations.     

Prophet Regions for Discounted,Uniformly Bounded Random Variables

Abstract

Let X ₁, X ₂,… be any sequence of [0,1]-valued random variables. A complete comparison is made between the expected maximum E(max _j≤n Y _j ) and the stop rule supremum sup _t E Y _t for two types of discounted sequences: (i) Y _j  = b _j X _j , where {b _j } is a nonincreasing sequence of positive numbers with b ₁ = 1; and (ii) Y _j  = B ₁… B _j?1 X _j , where B ₁, B ₂,… are independent [0,1]-valued random variables that are independent of the X _j , having a common mean β. For instance, it is shown that the set of points {(x, y): x = sup _t E Y _{{(x, y): x=sup t E Y} and y = E(max _j≤n Y _j ), for some sequence X ₁,…,X _n and Y _j  = b _j X _j }, is precisely the convex closure of the union of the sets {(b _j x, b _j y): (x, y) ∈ C _j }, j = 1,…,n, where C _j  = {(x, y):0 ≤ x ≤ 1, x ≤ y ≤ x[1 + (j ? 1)(1 ? x ^1/(j?1))]} is the prophet region for undiscounted random variables given by Hill and Kertz [8 Hill , T.P. , and R.P. Kertz . 1983 . Stop rule inequalities for uniformly bounded sequences of random variables . Trans. Amer. Math. Soc. 278 : 197 – 207 . [CSA]  [Google Scholar]]. As a special case, it is shown that the maximum possible difference E(max _j≤n β ^j?1 X _j ) ? sup _t E(β ^t?1 X _t ) is attained by independent random variables when β ≤ 27/32, but by a martingale-like sequence when β > 27/32. Prophet regions for infinite sequences are given also.     

Orderings of uniquely colorable hypergraphs

For a mixed hypergraph H=(X,C,D), where C and D are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every C∈C meets some class in more than one vertex, and every D∈D has a nonempty intersection with at least two classes. A vertex-orderx₁,x₂,…,x_n on X (n=|X|) is uniquely colorable if the subhypergraph induced by {x_j:1?j?i} has precisely one coloring, for each i (1?i?n). We prove that it is NP-complete to decide whether a mixed hypergraph admits a uniquely colorable vertex-order, even if the input is restricted to have just one coloring. On the other hand, via a characterization theorem it can be decided in linear time whether a given color-sequence belongs to a mixed hypergraph in which the uniquely colorable vertex-order is unique.     

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.     

Stochastic comparisons of order statistics from gamma distributions

Let (X₁,X₂,…,X_n) and (Y₁,Y₂,…,Y_n) be gamma random vectors with common shape parameter α(0<α?1) and scale parameters (λ₁,λ₂,…,λ_n), (μ₁,μ₂,…,μ_n), respectively. Let X₍₎=(X₍₁₎,X₍₂₎,…,X_(n)), Y₍₎=(Y₍₁₎,Y₍₂₎,…,Y_(n)) be the order statistics of (X₁,X₂,…,X_n) and (Y₁,Y₂,…,Y_n). Then (λ₁,λ₂,…,λ_n) majorizes (μ₁,μ₂,…,μ_n) implies that X₍₎ is stochastically larger than Y₍₎. However if the common shape parameter α>1, we can only compare the the first- and last-order statistics. Some earlier results on stochastically comparing proportional hazard functions are shown to be special cases of our results.     

On questions related to saturated chains of primes in polynomial rings

We propose to give positive answers to the open questions: is R(X,Y) strong S when R(X) is strong S? is R stably strong S (resp., universally catenary) when R[X] is strong S (resp., catenary)? in case R is obtained by a (T,I,D) construction. The importance of these results is due to the fact that this type of ring is the principal source of counterexamples. Moreover, we give an answer to the open questions: is R〈X₁,…,X_n〉 residually Jaffard (resp., totally Jaffard) when R(X₁,…,X_n) is ? We construct a three-dimensional local ring R such that R(X₁,…,X_n) is totally Jaffard (and hence, residually Jaffard) whereas R〈X₁,…,X_n〉 is not residually Jaffard (and hence, not totally Jaffard).     

Some stably tame polynomial automorphisms

We study the structure of length three polynomial automorphisms of R[X,Y] when R is a UFD. These results are used to prove that if SL_m(R[X₁,X₂,…,X_n])=E_m(R[X₁,X₂,…,X_n]) for all n≥0 and for all m≥3 then all length three polynomial automorphisms of R[X,Y] are stably tame.     

A harmonic analysis approach to essential normality of principal submodules

Guo and the second author have shown that the closure [I] in the Drury-Arveson space of a homogeneous principal ideal I in C[z₁,…,zn] is essentially normal. In this note, the authors extend this result to the closure of any principal polynomial ideal in the Bergman space. In particular, the commutators and cross-commutators of the restrictions of the multiplication operators are shown to be in the Schatten p-class for p>n. The same is true for modules generated by polynomials with vector-valued coefficients. Further, the maximal ideal space XI of the resulting C^?-algebra for the quotient module is shown to be contained in Z(I)∩∂Bn, where Z(I) is the zero variety for I, and to contain all points in ∂Bn that are limit points of Z(I)∩Bn. Finally, the techniques introduced enable one to study a certain class of weight Bergman spaces on the ball.     

A unique exchange property for bases

We define the concept of unique exchange on a sequence (X₁,…, X_m) of bases of a matroid M as an exchange of x ? X_i for y ? X_j such that y is the unique element of X_j which may be exchanged for x so that (X_i ? {x}) ∪ {y} and (X_j ? {y}) ∪ {x} are both bases. Two sequences X and Y are compatible if they are on the same multiset. Let UE(1) [UE(2)] denote the class of matroids such that every pair of compatible basis sequences X and Y are related by a sequence of unique exchanges [unique exchanges and permutations in the order of the bases]. We similarly define UE(3) by allowing unique subset exchanges. Then UE(1),UE(2), and UE(3) are hereditary classes (closed under minors) and are self-dual (closed under orthogonality). UE(1) equals the class of series-parallel networks, and UE(2) and UE(3) are contained in the class of binary matroids. We conjecture that UE(2) contains the class of unimodular matroids, and prove a related partial result for graphic matroids. We also study related classes of matroids satisfying transitive exchange, in order to gain information about excluded minors of UE(2) and UE(3). A number of unsolved problems are mentioned.     

Cyclic irreducible non-holonomic modules over the Weyl algebra: An algorithmic characterization

Let K be a field of characteristic zero, n≥1 an integer and A_n+1=K[X,Y₁,…,Y_n]〈∂_X,∂_Y1,…,∂_Yn〉 the (n+1)th Weyl algebra over K. Let S∈A_n+1 be an order-1 differential operator of the type with a_i,b_i∈K[X] and g_i∈K[X,Y_i] for every i=1,…,n. We construct an algorithm that allows one to recognize whether S generates a maximal left ideal of A_n+1, hence also whether A_n+1/A_n+1S is an irreducible non-holonomic A_n+1-module. The algorithm, which is a powerful instrument for producing concrete examples of cyclic maximal left ideals of A_n, is easy to implement and quite useful; we use it to solve several open questions.The algorithm also allows one to recognize whether certain families of algebraic differential equations have a solution in K[X,Y₁,…,Y_n] and, when they have one, to compute it.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

Prophet Regions for Independent [0, 1]-Valued Random Variables with Random Discounting

Abstract

Let X ₁, X ₂… and B ₁, B ₂… be mutually independent [0, 1]-valued random variables, with EB _j  = β > 0 for all j. Let Y _j  = B ₁ … sB _j?1 X _j for j ≥ 1. A complete comparison is made between the optimal stopping value V(Y ₁,…,Y _n ):=sup{EY _τ:τ is a stopping rule for Y ₁,…,Y _n } and E(max _1≤j≤n Y _j ). It is shown that the set of ordered pairs {(x, y):x = V(Y ₁,…,Y _n ), y = E(max _1≤j≤n Y _j ) for some sequence Y ₁,…,Y _n obtained as described} is precisely the set {(x, y):0 ≤ x ≤ 1, x ≤ y ≤ Ψ _{n, β}(x)}, where Ψ _{n, β}(x) = [(1 ? β)n + 2β]x ? β^?(n?2) x ² if x ≤ β ^n?1, and Ψ _{n, β}(x) = min _j≥1{(1 ? β)jx + β ^j } otherwise. Sharp difference and ratio prophet inequalities are derived from this result, and an analogous comparison for infinite sequences is obtained.     

Walking in circles

Consider the unit circle S¹ with distance function d measured along the circle. We show that for every selection of 2n points x₁,…,x_n,y₁,…,y_n∈S¹ there exists i∈{1,…,n} such that . We also discuss a game theoretic interpretation of this result.