Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Testing the equality of several covariance matrices with fewer observations than the dimension

For normally distributed data from the k populations with m×m covariance matrices Σ₁,…,Σ_k, we test the hypothesis H:Σ₁=?=Σ_k vs the alternative A≠H when the number of observations N_i, i=1,…,k from each population are less than or equal to the dimension m, N_i≤m, i=1,…,k. Two tests are proposed and compared with two other tests proposed in the literature. These tests, however, do not require that N_i≤m, and thus can be used in all situations, including when the likelihood ratio test is available. The asymptotic distributions of the test statistics are given, and the power compared by simulations with other test statistics proposed in the literature. The proposed tests perform well and better in several cases than the other two tests available in the literature.     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B_p,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,k are of the form (μ,π), where μ is a pairing on {1,…,2p}, π is a partition into k blocks of the same set, and a certain relation holds between μ and π. (The set partitions π that can appear in B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,k identifies it with a set of objects of the form (ρ,t), where ρ is a pairing on a 2(p-k+1)-subset of {1,…,2p} (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when p=k-1, then ρ is empty, and our bijection reduces to a well-known tree bijection.     

Steiner intervals, geodesic intervals, and betweenness

The concept of the k-Steiner interval is a natural generalization of the geodesic (binary) interval. It is defined as a mapping S:V×?×V?2^V such that S(u₁,…,u_k) consists of all vertices in G that lie on some Steiner tree with respect to a multiset W={u₁,…,u_k} of vertices from G. In this paper we obtain, for each k, a characterization of the class of graphs in which every k-Steiner interval S has the so-called union property, which says that S(u₁,…,u_k) coincides with the union of geodesic intervals I(u_i,u_j) between all pairs from W. It turns out that, as soon as k>3, this class coincides with the class of graphs in which the k-Steiner interval enjoys the monotone axiom (m), respectively (b2) axiom, the conditions from betweenness theory. Notably, S satisfies (m), if x₁,…,x_k∈S(u₁,…,u_k) implies S(x₁,…,x_k)⊆S(u₁,…,u_k), and S satisfies (b2) if x∈S(u₁,u₂,…,u_k) implies S(x,u₂,…,u_k)⊆S(u₁,…,u_k). In the case k=3, these three classes are different, and we give structural characterizations of graphs for which their Steiner interval S satisfies the union property as well as the monotone axiom (m). We also prove several partial observations on the class of graphs in which the 3-Steiner interval satisfies (b2), which lead to the conjecture that these are precisely the graphs in which every block is a geodetic graph with diameter at most two.     

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.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Unextendible product bases and 1-factorization of complete graphs

Let f(k₁,…,k_m) be the minimal value of size of all possible unextendible product bases in the tensor product space . We have trivial lower bounds and upper bound k₁?k_m. Alon and Lovász determined all cases such that f(k₁,…,k_m)=n(k₁,…,k_m). In this paper we determine all cases such that f(k₁,…,k_m)=k₁?k_m by presenting a sharper upper bound. We also determine several cases such that f(k₁,…,k_m)=n(k₁,…,k_m)+1 by using a result on 1-factorization of complete graphs.     

Maximum vertex and face degree of oblique graphs

Let G=(V,E,F) be a 3-connected simple graph imbedded into a surface S with vertex set V, edge set E and face set F. A face α is an 〈a₁,a₂,…,a_k〉-face if α is a k-gon and the degrees of the vertices incident with α in the cyclic order are a₁,a₂,…,a_k. The lexicographic minimum 〈b₁,b₂,…,b_k〉 such that α is a 〈b₁,b₂,…,b_k〉-face is called the type of α.Let z be an integer. We consider z-oblique graphs, i.e. such graphs that the number of faces of each type is at most z. We show an upper bound for the maximum vertex degree of any z-oblique graph imbedded into a given surface. Moreover, an upper bound for the maximum face degree is presented. We also show that there are only finitely many oblique graphs imbedded into non-orientable surfaces.     

Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

Formulas of Liapunov functions for systems of linear partial differential equations

Formulas of explicit quadratic Liapunov functions for showing asymptotic stability of the system of linear partial differential equations on (0,∞)×Ω, are constructed, where A is an n×n real matrix, u=T(u₁,u₂,…,un), Ω is a bounded domain in Rk with smooth boundary ∂Ω, and Δ denotes the Laplacian operator on Rk with Δu=T(Δu₁,Δu₂,…,Δun). These formulas are also modified and applied to a number of nonautonomous linear and nonlinear systems and models in structural stability, traveling wave, and Navier-Stokes equations.     

Regularity of patterns in the factorization of n!

Consider the multiplicities ep₁(n),ep₂(n),…,epk(n) in which the primes p₁,p₂,…,pk appear in the factorization of n!. We show that these multiplicities are jointly uniformly distributed modulo (m₁,m₂,…,mk) for any fixed integers m₁,m₂,…,mk, thus improving a result of Luca and St?nic? [F. Luca, P. St?nic?, On the prime power factorization of n!, J. Number Theory 102 (2003) 298-305]. To prove the theorem, we obtain a result regarding the joint distribution of several completely q-additive functions, which seems to be of independent interest.     

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.     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

Splitting multidimensional necklaces

The well-known “splitting necklace theorem” of Alon [N. Alon, Splitting necklaces, Adv. Math. 63 (1987) 247-253] says that each necklace with k⋅ai beads of color i=1,…,n, can be fairly divided between k thieves by at most n(k−1) cuts. Alon deduced this result from the fact that such a division is possible also in the case of a continuous necklace [0,1] where beads of given color are interpreted as measurable sets Ai⊂[0,1] (or more generally as continuous measures μi). We demonstrate that Alon's result is a special case of a multidimensional consensus division theorem about n continuous probability measures μ₁,…,μn on a d-cube d[0,1]. The dissection is performed by m₁+?+md=n(k−1) hyperplanes parallel to the sides of d[0,1] dividing the cube into m₁⋅?⋅md elementary cuboids (parallelepipeds) where the integers mi are prescribed in advance.     

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.     

Enumeration of (p,q)-parking functions

Parking functions are central in many aspects of combinatorics. We define in this communication a generalization of parking functions which we call (p₁,…,p_k)-parking functions. We give a characterization of them in terms of parking functions and we show that they can be interpreted as recurrent configurations in the sandpile model for some graphs. We also establish a correspondence with a Lukasiewicz language, which enables to enumerate (p₁,…,p_k)-parking functions as well as increasing ones.     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

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.

     

Construction of nonnegative symmetric matrices with given spectrum

Let σ = (λ₁, … , λ_n) be the spectrum of a nonnegative symmetric matrix A with the Perron eigenvalue λ₁, a diagonal entry c and let τ = (μ₁, … , μ_m) be the spectrum of a nonnegative symmetric matrix B with the Perron eigenvalue μ₁. We show how to construct a nonnegative symmetric matrix C with the spectrum

(λ₁+max{0,μ₁-c},λ₂,…,λ_n,μ₂,…,μ_m).