On some combinatorial questions in finite-dimensional spaces

Bounds are given for supinf∥Σ^p_i=1ν_i∥, where sup is taken over all set systems V₁,…, V_p of Rⁿ with 0∈∩^p_i=1convV_i and sup_v∈Vi∥ν∥?1 for i=1,…, p, and inf is taken over all possible choices ν_i∈V_i for i=1,…, p. Another similar problem is considered. The bounds are sharp.     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

The inertia of a Hermitian matrix having prescribed diagonal blocks

For i=1,…,m let H_i be an n_i×n_i Hermitian matrix with inertia In(H_i)= (π_i, ν_i, δ_i). We characterize in terms of the π_i, ν_i, δ_i the range of In(H) where H varies over all Hermitian matrices which have a block decomposition H= (X_ij)_{i, j=1,…, m} in which X_ij is n_i×n_j and X_ii=H_i.     

Representing the GCD as linear combination in non-PID rings

We prove the following fact: If finitely many elements p ₁,p ₂,…,p _n of a unique factorization domain are given such that the greatest common divisor of each pair (p _i ,p _j ) can be expressed as a linear combination of p _i and p _j , then the greatest common divisor of all the p _i ’s can also be expressed as a linear combination of p ₁,…,p _n . We prove an analogous statement in general commutative rings.     

On the multiplicative structure of odd perfect numbers

Starting with Euler's theorem that any odd perfect number n has the form n = p^ep_i^2e_i … p_k^2e_k, where p, p₁,…,p_k are distinct odd primes and p ≡ e ≡ 1 (mod 4), we show that extensive subsets of these numbers (so described) can be eliminated from consideration. A typical result says: if p^e, p_i^2e_i,…,p_r^2e_r are all of the prime-power divisors of such an n with p ≡ p_i ≡ 1 (mod 4), then the ordered set {e₁,…,e_r} contains an even number or odd number of odd numbers according as e ≡ pore ≡ p (mod 8).     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

A class of hypergraphs satisfying an inequality of Lovász

The following theorem is proved: Suppose that H = (X; E₁, E₂, …, E_m) is a hypergraph without odd cycles with n vertices and p components, such that any two edges have at most k vertices in common. If for any cycle C in H, there exist two vertices of C contained in at least two common edges of H, then Σ_i=1^m (|E_i| ? k) ≤ n ? pk.     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Uneven Splitting of Ham Sandwiches

Let μ ₁,…,μ _n be continuous probability measures on ? ⁿ and α ₁,…,α _n ∈[0,1]. When does there exist an oriented hyperplane H such that the positive half-space H ⁺ has μ _i (H ⁺)=α _i for all i∈[n]? It is well known that such a hyperplane does not exist in general. The famous Ham Sandwich Theorem states that if $\alpha_{i}=\frac{1}{2}Let μ ₁,…,μ _n be continuous probability measures on ℝ ⁿ and α ₁,…,α _n ∈[0,1]. When does there exist an oriented hyperplane H such that the positive half-space H ⁺ has μ _i (H ⁺)=α _i for all i∈[n]? It is well known that such a hyperplane does not exist in general. The famous Ham Sandwich Theorem states that if a_i=\frac12\alpha_{i}=\frac{1}{2} for all i, then such a hyperplane always exists.     

On a combinatorial problem of Erdös,Ginzburg, and Ziv

The following theorem is proved. If g₁,…,g_2n?1 is a sequence of 2n ? 1 elements in a finite group of order n (written additively), then there are n distinct indices i₁,…,i_n such that g_i1 + … + g_in = 0.     

A result on hypothesis testing for a multivariate normal distribution when some observations are missing

Let U_i = (X_i, Y_i), i = 1, 2,…, n, be a random sample from a bivariate normal distribution with mean μ = (μ_x, μ_y) and covariance matrix

. Let X_i, i = n + 1,…, N represent additional independent observations on the X population. Consider the hypothesis testing problem H₀ : μ = 0 vs. H₁ : μ ≠ 0. We prove that Hotelling's T² test, which uses (X_i, Y_i), i = 1, 2,…, n (and discards X_i, i = n + 1,…, N) is an admissible test. In addition, and from a practical point of view, the proof will enable us to identify the region of the parameter space where the T²-test cannot be beaten. A similar result is also proved for the problem of testing μ_x ? μ_y = 0. A Bayes test and other competitors which are similar tests are discussed.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

Counting permutations by successions and other figures

Let π=(π(1), π(2),…, π(n)) be a permutation of the arbitrary n-set S of positive integers. A p-succession (alternately, p-rise) in π is any pair π(i), π(i+1) with π(i+1)=π(i)+1p, i=1,2,…, n-1 (alternately, π(i+1)?π(i)+p). A succession (alternately, rise) is just a p-succession (alternately, p-rise) with p=1. A p-run in π is a subsequence i, i+1,…,i+p-1 of the permutation π. We show that the number of permutations of S which have precisely α rises and β successions depends only on n=¦S¦, α, β, and l, where l is the number of maximal subsets {i,i+1,…,i+j)} of S, and determine an explicit recursion and generating function for these numbers. The same methodology is applied to count permutations of S by number of rises and figures of a more general type, where a specific criterion characterizes such figures. As a special case, we obtain the generating function when the figure is a p-run. Finally, we enumerate permutations of S by number of p-successions. Additional results are provided relating this particular enumeration problem to the special case of ordinary successions (p=1).     

Permanence and Positive Periodic Solutions for Kolmogorov Competing Species Systems

We prove the existence of periodic solutions in a compact attractor of (R⁺)ⁿ for the Kolmogorov system x′_i = x_if_i(t, x₁, …, x_n), i = l, …, n in the competitive case. Extension to differential delay equations are con- sidered too. Applications are given to Lotka-Volterra systems with periodic coefficients.