Subsets of a finite set that intersect each other in at most one element

In this paper we study de Bruijn-Erdös type theorems that deal with the foundations of finite geometries. The following theorem is one of our main conclusions. Let S₁,…, S_n be n subsets of an n-set S. Suppose that |S_i| ? 3 (i = 1,…,n) and that |S_i ∩ S_j| ? 1 (i ≠ j;i,j = 1,…,n). Suppose further that each S_i has nonempty intersection with at least n ? 2 of the other subsets. Then the subsets S₁,…,S_n of S are one of the following configurations. (1) They are a finite projective plane. (2) They are a symmetric group divisible design and each subset has nonempty intersection with exactly n ? 2 of the other subsets. (3) We have n = 9 or n = 10 and in each case there exists a unique configuration that does not satisfy (1) or (2).     

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

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

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}$.     

On λ-designs

A λ-design is a system of subsets S₁, S₂,…, S_n from an n-set S, n > 3, where |S_i ∩ S_j| = λ for i ≠ j, |S_j| = k_j > λ > 0, and not all k_j, are equal. Ryser [9] and Woodall [101 have shown that each element of S occurs either r₁, or r₂ times (r₁ ≠ r₂) among the sets S₁,…, S_n and r₁ +r₂ = n + 1. Here we: (i) mention most of what is currently known about λ-designs; (ii) provide simpler proofs of some known results; (iii) present several new general theorems; and (iv) apply our theorems and techniques to the calculation of all λ-designs for λ ? 5. In fact, this calculation has been done for all λ ?/ 9 and is available from the author.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

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′}.     

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

An improved upper bound in the maximum dispersal problem

For integral? m?2, let x₁,…, x_m be any unit vectors in R_n, the real Euclidean space of n dimensions. We obtain an upper bound for the quantity min_i≠j|x_i-x_j| which, though not as simple, is uniformly sharper than one recently obtained by the author. The result has application to the so-called maximum-dispersal problem, an open problem recently popularized by Klee.     

Subsequence numbers and logarithmic concavity

Let S be a finite sequence of length r whose terms come from the finite alphabet a. The subsequence number of S (i = 0…r) is the number of distinct t-long subsequences of S. We prove (1) for r and a fixed, the S simultaneously attain their maximum possible values if and only if S is a repeated permutation of a (meaning no letters appears twice in S without all of the other letters of a intervening): (2) the numbers S…S……S, are logarithmically concave: and (3) over any central interval S…S……S…(iSr ? i). S, is least (through perhaps not uniquely). In addition, we show that for the generalized binomial coefficients c(i.j.n) defined by (1+x+…+ x^m?1)¹ = Σc(i.j.n)x¹, the sequence c(i ? 1.1.n), c(i?2.2n)… is strongly logarithmically concave, thus extending a result of S.M. Tanny and M. Zuker. Logarithmic concavity is treated in the context of triangular arrays of numbers.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

On positional games

Let {A_i} be a family of sets and let S = ∩_iA_i. By a positional game we shall mean a game played by two players on {A_i}. The players alternately pick elements of S and that player wins who fist has all the elements of one of the A_i. This paper deals with almost disjoint hypergraphs only, i.e., |A_i∪A_j| ? 1 if i ≠ j. Let $\text{M}{}^1\text{(n)}$ be the smallest integer for which there is an almost disjoint n-uniform hypergraph $\text{|T| = M}{}^1\text{(n)}$, so that the first player has a winning strategy. It is shown that $\text{lim}{}_{\mathrm{n}}\text{[M}{}^1\text{(n)]}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 4}$, which was conjectured by Erdös. The same method is applied to prove a conjecture of Hales and Jewett on r-dimensional tick-tack-toe if r is large enough. Finally we prove that for an arbitrary almost disjoint n-uniform hypergraph the second player has such a strategy that the first player unable to win in his mth move if m < (2 ? ?)ⁿ.     

Presentations of alternating semigroups

One presentation of the alternating groupA _n hasn?2 generatorss ₁,…,s_n?2 and relationss ₁ ³ =s _i ² =(s_1?1s_i)³=(s_js_k)²=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupA _n ^c )A _n is introduced: It hasn?1 generatorss ₁,…,S _n?2,e, theA _n-relations (above), and relationse ²=e, (es ₁)⁴, (es _j)²=(es _j)⁴,es _i=s _i s ₁ ^-1 es ₁, wherej>1 andi≥1.     

Decomposable bilinear numerical radii

Let A be an n-square normal matrix over $\text{C}$, and Q_{m, n} be the set of strictly increasing integer sequences of length m chosen from 1,…, n. For α,β∈Q_{m, n} denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k∈{0,1,…,m} write z.sfnc;α∩β|=k if there exists a rearrangement of 1,…,m, say i₁,…,i_k, i_k+1,…,i_m, such that α(i_j)=β(i_j), j=1,…,k, and {α(i_k+1),…,α(i_m)};∩{β(i_k+1),…,β(i_m)}=ø. Let

be the group of n-square unitary matrices. Define the nonnegative number

$\text{?}{}_{\mathrm{k}}\text{(A)=}\text{max}\text{U∈}\textcolor{red}{}\text{|}\text{det}\text{(U}{}^1\text{AU) [α|β]|}$

, where |α∩β|=k. Theorem 1 establishes a bound for ?_k(A), 0?k<m?1, in terms of a classical variational inequality due to Fermat. Let A be positive semidefinite Hermitian, n?2m. Theorem 2 leads to an interlacing inequality which, in the case n=4, m=2, resolves in the affirmative the conjecture that

$\text{?}{}_{\mathrm{m}}\text{(A)??}{}_{\mathrm{m?1}}\text{(A)????}{}_0\text{(A)}$

.     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

A constructive proof for a theorem on contractive mappings in power sets

Recently I proved the following theorem: To every positive integer m there exists a positive integer h such that the following holds: If S is a set of h elements and f a mapping of the power set B of S into B such that f(T)?T for all T?B, then there exists a strictly increasing sequence T₁?…?T_m of subsets of S such that one of the following three possibilities holds: (a) All sets f(T_i), i=1,…,m, are equal. (b) For all i=1,…,m we have f(T_i)=T_i (c) T_i=f(T_i+1) for all i=1,…,m?1.The proof given in [2] was non-constructive. In this paper now we give a constructive proof. By the way, this also yields a solution of a problem of Rado [3, p. 106].     

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.     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.