The minimum independence number for designs

Fort=2,3 andk2t–1 we prove the existence oft–(n,k,) designs with independence numberC _,k n ^{(k–t)/(k–1)} (ln n) ^1/(k–1) . This is, up to the constant factor, the best possible.Some other related results are considered.Supported by NSF Grant DMS-9011850     

Circle grids and bipartite graphs of distances

Fort fixed,n+t pointsA ₁,A ₂,...,A _n andB ₁,B ₂,...,B _t are constructed in the plane withO(n) distinct distancesd(A _i B _j ) As a by-product we show that the graph of thek largest distances can contain a complete subgraphK _{t, n} withn=(k ²), which settles a problem of Erds, Lovász and Vesztergombi.Research partially supported by the Hungarian National Science Fund (OTKA) # 2117.     

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

Resolvable Mendelsohn designs with block size 4

Summary Letv andK be positive integers. A (v, k, 1)-Mendelsohn design (briefly (v, k, 1)-MD) is a pair (X,B) whereX is av-set (ofpoints) andB is a collection of cyclically orderedk-subsets ofX (calledblocks) such that every ordered pair of points ofX are consecutive in exactly one block ofB. A necessary condition for the existence of a (v, k, 1)-MD isv(v–1) 0 (modk). If the blocks of a (v, k, 1)-MD can be partitioned into parallel classes each containingv/k blocks wherev ) (modk) or (v – 1)/k blocks wherev 1 (modk), then the design is calledresolvable and denoted briefly by (v, k, 1)-RMD. It is known that a (v, 3,1)-RMD exists if and only ifv 0 or 1 (mod 3) andv 6. In this paper, it is shown that the necessary condition for the existence of a (v, 4, 1)-RMD, namelyv 0 or 1 (mod 4), is also sufficient, except forv = 4 and possibly exceptingv = 12. These constructions are equivalent to a resolvable decomposition of the complete symmetric directed graphK _v ^* onv vertices into 4-circuits.Research supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-5320.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

Random k-dimensional orders: Width and number of linear extensions

We consider the width W _k (n) and number L _k (n) of linear extensions of a random k-dimensional order P _k (n). We show that, for each fixed k, almost surely W _k (n) lies between (k/2–C)n _1–1/k and 4kn ^1-1/k , for some constant C, and L _k (n) lies between (e ^-2 n ^1-1/k ) ⁿ and (2kn ^1-1/k ) ⁿ . The bounds given also apply to the expectations of the corresponding random variables. We also show that W _k (n) and log L _k (n) are sharply concentrated about their means.     

Exponential-cosine operator-valued functional equation in the strong operator topology

LetX be a Banach Space and letB(X) denote the family of bounded linear operators onX. LetR ⁺ = [0, ). A one parameter family of operators {S(t);t R ⁺},S:R ⁺ B(X), is called exponential-cosine operator function ifS(O) =I andS(s +t) – 2S(s)S(t) = (S(2s) – 2S ²(s))S(t –s), for alls, t R ⁺,s t. Let ,fD(A), and ,fD(B). It is shown that for a strongly continuous exponential-cosine operator {S(t)},fD(A ²) implies ₀ ^t (t –u(S(u)fduD(B) and B ₀ ^t (t –u)S(u)fdu =S(t)f –f +tAf – 2A ₀ ^t S(u)fdu + 2A ² ₀ ^t (t –u)S(u)fdu.D(B) is seen to be dense inD(A ²). Some regularity properties ofS(t) have also been obtained.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Control of stochastic distributed-parameter systems

A scheme is proposed for the feedback control of distributed-parameter systems with unknown boundary and volume disturbances and observation errors. The scheme consists of employing a nonlinear filter in the control loop such that the controller uses the optimal estimates of the state of the system. A theoretical comparison of feedback proportional control of a styrene polymerization reactor with and without filtering is presented. It is indicated how an approximate filter can be constructed, greatly reducing the amount of computing required.Notation a(t) l-vector noisy dynamic input to system - A(t, a) l-vector function - A frequency factor for first-order rate law (5.68×10⁶ sec^–1) - b distance to the centerline between two coil banks in the reactor (4.7 cm) - B k-vector function defining the control action - c(, ) concentration of styrene monomer, molel ^–1 - C _p heat capacity (0.43 cal · g^–1 · K^–1) - C _ij constants in approximate filter, Eqs. (49)–(52) - E activation energy (20330 cal · mole^–1) - expectation operator - f(t,...) n-vector function - g ₀,g ₁(t,...) n-vector functions - h(t, u) m-vector function relating observations to states - H(t) function defined in Eq. (36) - k dimensionality of control vectorv(x, t) - k _i constants in approximate filter, Eqs. (49)–(52) - K dimensionless proportional gain - l dimensionality of dynamic inputa(t) - m dimensionality of observation vectory(t) - n dimensionality of state vectoru(x, t) - P ^(vv)(x, s, t) n×n matrix governed by Eq. (9) - P ^(va)(x, t) n×l matrix governed by Eq. (10) - P ^(aa)(t) l×l matrix governed by Eq. (11) - q _i (t) diagonal elements ofm×m matrixQ(x, s, t) - Q(x, s, t) m×m weighting matrix - R universal gas constant (1.987 cal · mole^–1 · K^–1) - R(x, s, t) n×n weighting matrix - R _i (t) n×n weighting matrix - s dimensionless spatial variable - S(x, s, t) matrix defined in Eq. (11) - t dimensionless time variable - T(, ) temperature, K - u(x, t) n-dimensional state vector - u _c (t) wall temperature - u _d desired value ofu ₁(1,t) - u _c * reference control value ofu _c - u _c ^max maximum value ofu _c - u _c ^min minimum value of _c - v(x, t) k-dimensional control vector - W(t) l×l weighting matrix - x dimensionless spatial variable - y(t) m-dimensional observation vector - _i constants in approximate filter, Eqs. (49)–(52) - dimensionless parameter defined in Eq. (29) - H heat of reaction (17500 cal · mole^–1) - dimensionless activation energy, defined in Eq. (29) - (x) Dirac delta function - (x, t) m-dimensional observation noise - thermal conductivity (0.43×10^–3 cal · cm^–1 · sec^–1 · K^–1) - density (1 g · cm^–3) - time, sec - dimensionless parameter defined in Eq. (29) - spatial variable, cm - * reference value - ^ estimated value     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

Simple minimum coverings ofK n with copies ofK 4 −e

Summary AK ₄–e design of ordern is a pair (S, B), whereB is an edge-disjoint decomposition ofK _n (the complete undirected graph onn vertices) with vertex setS, into copies ofK ₄–e, the graph on four vertices with five edges. It is well-known [1] thatK ₄–e designs of ordern exist for alln 0 or 1 (mod 5),n 6, and that if (S, B) is aK ₄–e design of ordern then |B| =n(n – 1)/10.Asimple covering ofK _n with copies ofK ₄–e is a pair (S, C) whereS is the vertex set ofK _n andC is a collection of edge-disjoint copies ofK ₄–e which partitionE(K_n)P, for some . Asimple minimum covering ofK _n (SMCK _n) with copies ofK ₄–e is a simple covering whereP consists of as few edges as possible. The collection of edgesP is called thepadding. Thus aK ₄–e design of ordern isSMCK _n with empty padding.We show that forn 3 or 8 (mod 10),n 8, the padding ofSMCK _n consists of two edges and that forn 2, 4, 7 or 9 (mod 10),n 9, the padding consists of four edges. In each case, the padding may be any of the simple graphs with two or four edges respectively. The smaller cases need separate treatment:SMCK ₅ has four possible paddings of five edges each,SMCK ₄ has two possible paddings of four edges each andSMCK ₇ has eight possible paddings of four edges each.The recursive arguments depend on two essential ingredients. One is aK ₄–e design of ordern with ahole of sizek. This is a triple (S, H, B) whereB is an edge-disjoint collection of copies ofK ₄–e which partition the edge set ofK _n\K_k, whereS is the vertex set ofK _n, and is the vertex set ofK _k. The other essential is acommutative quasigroup with holes. Here we letX be a set of size 2n 6, and letX = {x ₁, x₂, ..., x_n} be a partition ofX into 2-element subsets, calledholes of size two. Then a commutative quasigroup with holesX is a commutative quasigroup (X, ) such that for each holex _i X, (x_i, ) is a subquasigroup. Such quasigroups exist for every even order 2n 6 [4].     

On the uniqueness of a Walsh series converging on subsequences of partial sum

We show that if a Walsh series whose coefficients tend towards zero is such that the subsequence of its partial sums indexed by n_k, where n_k satisfies the condition 2^k–1k2^k (k=0, 1, 2, ...), tends everywhere, except possibly for a denumerable set, towards a bounded functionf(x), then this series is the Fourier series of the functionf(x).Translated from Matematicheskie Zametki, Vol. 16, No. 1, pp. 27–32, July, 1974.     

An Explicit Construction for a Ramsey Problem

An explicit coloring of the edges of K_n is constructed such that every copy of K₄ has at least four colors on its edges. As n , the number of colors used is n^1/2+o(1). This improves upon the previous bound of O(n^2/3) due to Erds and Gyárfás obtained by probabilistic methods. The exponent 1/2 is optimal, since it is known that at least (n^1/2) colors are required in such a coloring.The coloring is related to constructions giving lower bounds for the multicolor Ramsey number r_k(C₄). It is more complicated however, because of restrictions imposed on interactions between color classes.* Research supported in part by NSF Grant No. DMS–9970325.     

Connectedness and diameter for random orders of fixed dimension

Let P _k (n) be the (partial) order determined by intersecting k random linear orderings of a set of size n; equivalently, let P _k (n) consist of n points chosen randomly and independently from the unit cube in ^k , with the induced product order. We show for each fixed k>1, that with probability approaching 1 as n, the comparability graph of P _k (n) is connected and has diameter 3.