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).     

Sieve-equivalence and explicit bijections

Suppose A₁,…, A_n are subsets of a finite set A, and B₁,…, B_n are subsets of a finite set B. For each subset S of N = {1, 2,…, n}, let A_s = ∩_i?SA_i and B_S = ∩_i?SB_i. It is shown that if explicit bijections f_S:A_S → B_S for each S ? N are given, an explicit bijection h:A-∪_i=1A_i→B-∪_i=1B_i can be constructed. The map h is independent of any ordering of the elements of A and B, and of the order in which the subsets A_i and B_i are listed.     

Intersection patterns of convex sets

LetK ₁,…K_n be convex sets inR ^d. For 0≦i denote byf _ithe number of subsetsS of {1,2,…,n} of cardinalityi+1 that satisfy ∩{K _i∶i∈S}≠Ø. We prove:Theorem.If f _d+r=0 for somer r>=0, then {fx161-1} This inequality was conjectured by Katchalski and Perles. Equality holds, e.g., ifK ₁=…=K_r=R^d andK _r+1,…,K_n aren?r hyperplanes in general position inR ^d. The proof uses multilinear techniques (exterior algebra). Applications to convexity and to extremal set theory are given.     

Multiplicative representations of integers

Lehh ≧ 2, and let ?=(B ₁, …,B _h ), whereB ₁ ? N={1, 2, 3, …} fori=1, …,h. Denote by g_?(n) the number of representations ofn in the formn=b ₁ …b _h , whereb _i ∈B _i . If v (n) > 0 for alln >n ₀, then ? is anasymptotic multiplicative system of order h. The setB is anasymptotic multiplicative basis of order h ifn=b ₁ …b _n is solvable withb _i ∈B for alln >n ₀. Denote byg(n) the number of such representations ofn. LetM(h) be the set of all pairs (s, t), wheres=lim g_? (n) andt=lim g_? (n) for some multiplicative system ? of orderh. It is proved that {fx129-1} In particular, it follows thats ≧ 2 impliest=∞. A corollary is a theorem of Erdös that ifB is a multiplicative basis of orderh ≧ 2, then lim g_? g(n)=∞. Similar results are obtained for asymptotic union bases of finite subsets of N and for asymptotic least common multiple bases of integers.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Construction of a Jacobi matrix from spectral data

A proof is given for the existence and uniqueness of a correspondence between two pairs of sequences {a},{b} and {ω},{μ}, satisfying b_i>0 for i=1,…,n?1 and ω₁<μ₁<?<μ_n?1<ω_n, under which the symmetric Jacobi matrices J(n,a,b) and J(n?1,a,b) have eigenvalues {ω} and {μ} respectively. Here J(m,a,b) is symmetric and tridiagonal with diagonal elements a_i (i=1,…,m) and off diagonal elements b_i (i=1,…,m?1). A new concise proof is given for the known uniqueness result. The existence result is new.     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

A localization inequality for set functions

We prove the following theorem, which is an analog for discrete set functions of a geometric result of Lovász and Simonovits. Given two real-valued set functions f₁,f₂ defined on the subsets of a finite set S, satisfying for i∈{1,2}, there exists a positive multiplicative set function μ over S and two subsets A,B⊆S such that for i∈{1,2}μ(A)f_i(A)+μ(B)f_i(B)+μ(A∪B)f_i(A∪B)+μ(A∩B)f_i(A∩B)?0. The Ahlswede-Daykin four function theorem can be deduced easily from this.     

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.     

The asymptotic ruin problem when the healthy and sick periods form an alternating renewal process

Let {T₁, Y₁}^∞_i=1 be a sequence of positive independent random variables. Let, also, Z₁ = βY′₁ ? πT_i, i = 1, 2, …, where Y′₁ = Max(0, Y_i ? w), w ? 0, and where β < 0 and π is such that E(Z₁) < 0. We consider the random walk of partial sums S_n = ?ⁿ_i=1Z_i in the presence of an absorbing region (u, ∞), u ? 0, and S₀ ≡ 0. Of interest is $\text{ψ(u) = Pr(}\text{S}\text{?}\text{≤ u)}$ where S? = Sup(0, S₁, S₂, …, S_n, …).     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

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.     

Simultaneous block diagonalization of two real symmetric matrices

The simultaneous diagonalization of two real symmetric (r.s.) matrices has long been of interest. This subject is generalized here to the following problem (this question was raised by Dr. Olga Taussky-Todd, my thesis advisor at the California Institute of Technology): What is the first simultaneous block diagonal structure of a nonsingular pair of r.s. matrices ? For example, given a nonsingular pair of r.s. matrices S and T, which simultaneous block diagonalizations X′SX = diag(A₁, , A_k), X′TX = diag(B₁,, B_k) with dim A_i = dim B_i and X nonsingular are possible for 1 ? k ? n; and how well defined is a simultaneous block diagonalization for which k, the number of blocks, is maximal? Here a pair of r.s. matrices S and T is called nonsingular if S is nonsingular.If the number of blocks k is maximal, then one can speak of the finest simultaneous block diagonalization of S and T, since then the sizes of the blocks A_i are uniquely determined (up to permutations) by any set of generators of the pencil P(S, T) = {aS + bT|a, tb ε R} via the real Jordan normal form of S^?1T. The proof uses the canonical pair form theorem for nonsingular pairs of r.s. matrices. The maximal number k and the block sizes dim A_i are also determined by the factorization over C of ? (λ, μ) = det(λS + μT) for λ, μ ε R.     

An application of L-functions of imaginary quadratic fields

Let F₁(x, y),…, F_2h+1(x, y) be the representatives of equivalent classes of positive definite binary quadratic forms of discriminant ?q (q is a prime such that q ≡ 3 mod 4) with integer coefficients, then the number of integer solutions of F_i(x, y) = n (i = 1,…, 2h + 1) can be calculated for each natural number n using L-functions of imaginary quadratic field $\text{Q}$((?q)^1/2).     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

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).     

Complementing and exactly covering sequences

The following is proved (in a slightly more general setting): Let α₁, …, α_m be positive real, γ₁, …, γ_m real, and suppose that the system [nα_i + γ_i], i = 1, …, m, n = 1, 2, …, contains every positive integer exactly once (= a complementing system). Then $\text{α}{}_{\mathrm{i}}\text{α}{}_{\mathrm{j}}$ is an integer for some i ≠ j in each of the following cases: (i) m = 3 and m = 4; (ii) m = 5 if all α_i but one are integers; (iii) m ? 5, two of the α_i are integers, at least one of them prime; (iv) m ? 5 and α_n ? 2ⁿ for n = 1, 2, …, m ? 4.For proving (iv), a method of reduction is developed which, given a complementing system of m sequences, leads under certain conditions to a derived complementing system of m ? 1 sequences.