A variation of Menger's theorem for long paths

In this paper we prove a Mengerian theorem for long paths, namely, that if in order to cut every uv-path of length at least n (n ≥ 2), in a diagraph D, we need to remove at least h points, then there exist {$\text{h}\text{(3n ? 5)}$} interior disjoint uv-paths in D of length at least n. Some variations and applications of this theorem are given as well.     

On the average size of the sets in a Sperner family

In this paper, we show that the average size of the elements of a Sperner family of subsets of an n-element set must exceed k if there are more than $\text{(}\text{n}\text{k}\text{)}$ in the family and $\text{k≤}\text{1}\text{2 n}$. A generalized dealing with sums of weights over a set is also proven.     

Retarded equations on the sphere induced by linear equations

Using a Poincaré compactification, the linear homogeneous system of delay equations {x = Ax(t ? 1) (A is an n × n real matrix) induces a delay system π(A) on the sphere Sⁿ. The points at infinity belong to an invariant submanifold S^{n ? 1} of Sⁿ. For an open and dense set of 2 × 2 matrices A with distinct eigenvalues, the system π(A) has only hyperbolic critical points (including the critical points at infinity). For an open and dense set of 2 × 2matrices $\text{A}$ with complex eigenvalues, the nonwandering set at infinity is the union of an odd number of hyperbolic periodic orbits; if $\text{(}\text{det}\text{A}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{<}\text{3π}\text{2}$, the restriction of $\text{π(}\text{A}\text{)}$ to S¹ is Morse-Smale. For n = 1 there exist periodic orbits of period 4 provided that $\text{?A >}\text{π}\text{2}$ and Hopf bifurcation of a center occurs for ?A near $\text{(}\text{π}\text{2}\text{) + 2kπ, k ? Z}$.     

Helly-type theorems about sets

Let A be a finite set and $\text{F}$ be a family of its subsets. Two players pick m resp. n points alternately from A. I wins if he picks all the points of some element of $\text{F}$, otherwise II wins. We give a sufficient condition for II to have a winning strategy. Using this we prove the following statement. If in Go-moku I occupies m places, and II occupies n places in each turn, then, in case of m?n, I may have an arbitrarily long row of his places; in case m?n, II may bound the lenght of the rows occupied I.     

On a set puncturing problem

It is established that the maximum number of points required to puncture 3n sets of probability $\text{2}\text{3n}$ is 2n, as had been conjectured. In fact, for 1 ≤ m ≤ n, a family of m sets of probability $\text{2}\text{n}$ can be punctured using no more than $\text{min}\text{(m,[}\text{(n + m)}\text{3}\text{])}$ points. The more general statement that (k + 1)n sets of probability $\text{k}\text{(k + 1)n}$ require at most 2n points for puncturing is shown to be false already for k = 3.     

Finite prime-field characteristic sets for planar configurations

Examples are constructed of planar matroids with finite prime-field characteristic sets (i.e. matroids representable over a finite set of prime fields but over fields of no other characteristic). In particular, for any n>3, a projectively unique integer matrix is constructed with 2lsqblog₂nrsqb+6 columns which often gives nonsingleton characteristic sets and, when n is prime, has characteristic set {n}. Many finite subsets of primes are shown to be characteristic sets, including {23,59} (the smallest pair found using these methods), all pairs of primes {p, p′:67?p<p′?293}, and the seventeen largest five-digit primes. Probabilistic arguments are presented to support the conjecture that prime-field characteristic sets exist of every finite cardinality. For p>3, AG(2,p) is shown to be a subset of PG(2, q) only for q=p^s. Another general construction technique suggests that when $\text{P}\text{={p}{}_1\text{,…,p}{}_{\mathrm{k}}\text{}}$ are the primitive prime divisors of 2ⁿ±1 (n sufficiently large), then there is a matroid with O (log n) points whose characteristic set is $\text{P}$. We remark that although only one finite nonsingleton characteristic set (due to R. Reid) was known prior to this paper, a new technique by J. Kahn has shown that every finite set of primes forms a (non-prime-field) characteristic set.     

Computing a perfect strategy for n × n chess requires time exponential in n

It is proved that a natural generalization of chess to an n × n board is complete in exponential time. This implies that there exist chess positions on an n × n chessboard for which the problem of determing who can win from that position requires an amount of time which is at least exponential in $\text{n}$.     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

Indecomposable triple systems

A t-design (λ, t, d, n) is a system $\text{B}$ of sets of size d from an n-set S, such that each t subset of S is contained in exactly λ elements of $\text{B}$. A t-design is indecomposable (written IND(λ, t, d, n)) if there does not exist a subset $\text{B}$ ? $\text{B}$ such that $\text{B}$ is a (λ, t, d, n) for some λ, 1 ? λ < λ. A triple system is a (λ; 2, 3, n). Recursive and constructive methods (several due to Hanani) are employed to show that: (1) an IND(2; 2, 3, n) exists for n ≡ 0, 1 (mod 3), n ? 4 and n ≡ 7 (designs of Bhattacharya are used here), (2) an IND(3; 2, 3, n) exists for n odd, n ? 5, (3) if an IND(λ, 2, 3, n) exists, n odd, then there exists an infinite number of indecomposable triple systems with that λ.     

γ-sets and other singular sets of real numbers

A family of $\text{J}$ of open subsets of the real line is called an ω-cover of a set X iff every finite subset of X is contained in an element of $\text{J}$. A set of reals X is a γ-set iff for every ω-cover $\text{J}$ of X there exists $\text{〈D}{}_{\mathrm{n}}\text{: n < ω〉?}\text{J}{}^{\mathrm{\omega }}$ such that

In this paper we show that assuming Martin's axiom there is a γ-set X of cardinality the continuum.     

On the number of k-subsets of a set of n points in the plane

For a configuration S of n points in $\text{E}$², H. Edelsbrunner (personal communication) has asked for bounds on the maximum number of subsets of size k cut off by a line. By generalizing to a combinatorial problem, we show that for 2k < n the number of such sets of size at most k is at most 2nk ? 2k² ? k. By duality, the same bound applies to the number of cells at distance at most k from a base cell in the cell complex determined by an arrangement of n lines in $\text{P}$².     

Codimension one spheres in Rn with double tangent balls

In contrast to the situation in $\text{R}$³, where a 2-sphere with double tangent balls at each point must be tamely embedded in $\text{R}$³, there exist wild (n?1)-spheres in $\text{R}$ⁿ for n>3 with this same geometric property. However, if the sphere Σ is tame moduio a subset X that lies in a polyhedron P that is tame in Σ, the dimension of P is less than n?2, n>4, and Σ has double tangent balls over X, then Σ must be tame in $\text{R}$ⁿ. Also if the tangent balls extend over P and are pairwise congruent, the dimensional restriction on P can be dropped. Examples are given to support the necessity of the hypotheses of the included theorems.     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.     

Waring's problem for the ring of polynomials

We investigate the question of which polynomials are not representable as the sum of “few” powers of polynomials. In particular for Waring's problem over the ring of polynomials we show that there exist polynomials which are not the sum of fewer than $\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$nth powers of polynomials.     

On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

A class of solutions to the gossip problem,part I

We characterize optimal solutions to the gossip problem in which no one hears his own information. That is, we consider graphs on n vertices where the edges are given a linear ordering such that an increasing path exists from each vertex to every other, but there is no increasing path from a vertex to itself. Such graphs exist if and only if n is even, in which case the fewest number of edges is 2n - 4, as in the original gossip problem (in which the “$\text{N}$o $\text{O}$ne $\text{H}$ears his $\text{O}$wn information” condition did not appear). We characterize optimal solutions of this sort, called NOHO-graphs, by a correspondence with quadruples consisting of two permutations and two binary sequences. The correspondence uses a canonical numbering of the vertices of the graph; it arises from the edge ordering. (Exception: there are two optimal solution graphs which do not meet this characterization.) Also in Part I, we show constructively that NOHO-graphs are Hamiltonian, bipartite, and planar. In Part II, we study other properties of the associated quadruples, which includes enumerating them. In Part III, we enumerate the non-isomorphic NOHO-graphs.     

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

Some special vapnik-chervonenkis classes

For a class $\text{C}$ of subsets of a set X, let V($\text{C}$) be the smallest n such that no n-element set F?X has all its subsets of the form A ∩ F, A ∈ $\text{C}$. The condition V($\text{C}$) <+∞ has probabilistic implications. If any two-element subset A of X satisfies both A ∩ C = Ø and A ? D for some C, D∈$\text{C}$, then $\text{V(}\text{C}\text{)=2}$ if and only if $\text{C}$ is linearly ordered by inclusion. If $\text{C}$ is of the form $\text{C}\text{={∩}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{C}{}_{\mathrm{i}}\text{:C}{}_{\mathrm{i}}\text{∈}\text{C}{}_{\mathrm{i}}$, i=1,2,…,n}, where each $\text{C}{}_{\mathrm{i}}$ is linearly ordered by inclusion, then $\text{V(}\text{C}\text{)?n+1}$. If H is an (n-1)-dimensional affine hyperplane in an n-dimensional vector space of real functions on X, and $\text{C}$ is the collection of all sets {x: f(x)>0} for f in H, then $\text{V(}\text{C}\text{)=n}$.     

Almost commuting matrices

It is shown that if A and B are n × n complex matrices with $\text{A = A}{}^1\text{and}\text{∥AB ? BA∥</}\text{2?}{}^2\text{(n ? 1)}$, then there exist n × n matrices A′ and B′ with $\text{A′ = A′}{}^1\text{such that}\text{A′B′ = B′A′}\text{and}\text{∥A ? A′∥? ?, ∥B ? B′∥? ?}$.     

A linear algorithm for nonhomogeneous spectra of numbers

Given a sequence of integers [a_i]_i=1ⁿ, an O(n) iterative algorithm is presented which decides whether there exist real numbers α and β such that a_i = [iα + β] (1 ? i ? n). In fact, the linear algorithm computes the partial quotients of the continued fraction expansions of $\text{d}$ and $\text{d}$ such that $\text{d < α <}\text{d}$ if and only if a_i = [iα + β] (1 ? i ? n) for suitable β = β(α).