Single change covering designs

A single-change covering designSC (v, k, b) on av-setV is a sequence ofb k-sets (blocks) onV which together cover every pair of elements ofV at least once, such that two successive blocks havek–1 elements in common. It is desirable to minimizeb. Some constructions and lower bounds forb are given.     

On the Spectra of Certain Graphs Arising from Finite Fields

Cayley graphs on a subgroup ofGL(3,p),p>3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The “1-dimensional” eigenvalues can be completely described, while a portion of the “higher dimensional” eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup ofGL(2,p). This method can be extended further to construct graphs using a subgroup ofGL(n, p) forn≥4. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs fromGL(2,p) andGL(3,p); this part of the spectra alone is sufficient to show that forn≥4, the graphs fromGL(n, p) are not in general Ramanujan.     

Commutative rings and binomial coefficients

We characterize commutative domainsR for which theR-module ofR-valued polynomials is generated by binomial coefficients. This turns out to be a special case of a more general result concerning commutative ringsR of zero characteristics in which fork=1,2,... and allxR the productx(x–1)·­.·(x–k+1) is divisible byk! inR.The work of the second author has been sponsored by the KBN grant 2 1037 91 01     

Frattini subgroups ofp-closed andp-supersolvable groups

A nonabelianp-group with cyclic center cannot occur as a normal subgroup contained in the Frattini subgroup of ap-closed group. If a nonabelian normal subgroup of orderp ⁿ and nilpotence classk is contained in the Frattini subgroup of ap-closed group, then its exponent is a divisor ofp ^n−k . This fact is used to derive a relation among the order, number of generators, exponent, and class of the Frattini subgroup, forp-groups. Finally, it is conjectured that a nonabelianp-group having center of orderp cannot occur as a normal subgroup contained in the Frattini subgroup of any finite group. A proof is given forp-supersolvable groups.     

Existence results for generalized balanced tournament designs with block size 3

A generalized balanced tournament design,GBTD(n, k) defined on akn-setV, is an arrangement of the blocks of a (kn, k, k–1)-BIBD defined onV into ann× (kn–1), array such that (1) every element ofV is contained in precisely one cell of each column, and (2) every element ofV is contained in at mostk cells of each row. In this paper, we completely determine the spectrum ofGBTD(n, 3). In addition we prove the exitence of factoredGBTD(n, 3) forn a positive integer,n4, with at most one possible exception.This research was supported by a Postdoctoral membership at the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455.     

Approximation ofk-Monotone Functions

It is shown that an algebraic polynomial of degree k−1 which interpolates ak-monotone functionfatkpoints, sufficiently approximates it, even if the points of interpolation are close to each other. It is well known that this result is not true in general for non-k-monotone functions. As an application, we prove a (positive) result on simultaneous approximation of ak-monotone function and its derivatives inL_p, 0<p<1, metric, and also show that the rate of the best algebraic approximation ofk-monotone functions (with bounded (k−2)nd derivatives inL_p, 1<p<∞, iso(n^−k/p).     

Padé-type approximants of exp (−z) whose denominators are (1+z/n) n

Summary In this paper, we show that the sequences of Padé-type approximants (k–1/k) and (k/k) converge to exp (–z), uniformly and geometrically on every compact subset of the plane. A numerical study has been done, which discriminates these sequences from the point of view ofA-acceptability.     

A problem of P. Seymour on nonbinary matroids

The following statement fork=1, 2, 3 has been proved by Tutte [4], Bixby [1] and Seymour [3] respectively: IfM is ak-connected non-binary matroid andX a set ofk-1 elements ofM, thenX is contained in someU ₄ ² minor ofM. Seymour [3] asks whether this statement remains true fork=4; the purpose of this note is to show that it does not and to suggest some possible alternatives. Supported in part by the National Science Foundation     

Lower bounds for coverings of pairs by large blocks

Letnkt be positive integers, andX—a set ofn elements. LetC(n, k, t) be the smallest integerm such that there existm k-tuples ofX B ₁ B ₂,...,B _m with the property that everyt-tuple ofX is contained in at least oneB _i . It is shown that in many cases the standard lower bound forC(n, k, 2) can be improved (k sufficiently large,n/k being fixed). Some exact values ofC(n, k, 2) are also obtained.     

Linking (n − 2)-dimensional panels inn-space I: (k − 1,k)-graphs and (k − 1,k)-frames

A (k – 1,k)-graph is a multi-graph satisfyinge (k – 1)v – k for every non-empty subset ofe edges onv vertices, with equality whene = |E(G)|. A (k – 1,k)-frame is a structure generalizing an (n – 2, 2)-framework inn-space, a structure consisting of a set of (n – 2)-dimensional bodies inn-space and a set of rigid bars each joining a pair of bodies using ball joints. We prove that a graph is the graph of a minimally rigid (with respect to edges) (k – 1,k)-frame if and only if it is a (k – 1,k)-graph. Rigidity here means infinitesimal rigidity or equivalently statical rigidity.     

Proof of a conjecture on the Sperner property of the subgroup lattice of an abelianp-group

Let (p) denote the subgroup lattice of the abelianp-group

An inverse theorem for the restricted set addition in Abelian groups

Let A be a set of k5 elements of an Abelian group G in which the order of the smallest nonzero subgroup is larger than 2k−3. Then the number of different elements of G that can be written in the form a+a^′, where a,a^′A, a≠a^′, is at least 2k−3, as it has been shown in [Gy. Károlyi, The Erdős–Heilbronn problem in Abelian groups, Israel J. Math. 139 (2004) 349–359]. Here we prove that the bound is attained if and only if the elements of A form an arithmetic progression in G, thus completing the solution of a problem of Erdős and Heilbronn. The proof is based on the so-called ‘Combinatorial Nullstellensatz.’     

Perfect matchings in regular bipartite graphs

P. Hall, [2], gave necessary and sufficient conditions for a bipartite graph to have a perfect matching. Koning, [3], proved that such a graph can be decomposed intok edge-disjoint perfect matchings if and only if it isk-regular. It immediately follows that in ak-regular bipartite graphG, the deletion of any setS of at mostk – 1 edges leaves intact one of those perfect matchings. However, it is not known what happens if we delete more thank – 1 edges. In this paper we give sufficient conditions so that by deleting a setS ofk + r edgesr 0, stillG – S has a perfect matching. Furthermore we prove that our result, in some sense, is best possible.     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

Toughness and the existence ofk-factors. II

In a paper with the same title [3], we proved Chvátal's conjecture thatk-tough graphs havek-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose|V(G)| k + 1,k |V(G)| even, and|S| k w(G – S) – 7/8k ifw(G – S) 2, wherew(G – S) is the number of connected components ofG – S. ThenG has ak-factor.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

A class of ((p n−p m)(p n−1), p n−p m)-arcs in PG(2, p n)

A (k, d)-arc in PG(2, q) is a set of k points such that some d, but no d+1, of them are collinear. An outstanding problem is to find the maximum value of k for which a (k, d)-arc exists. A construction is given for a class of (k, p ⁿ–p ^m)-arcs in PG(2, p ⁿ). These arcs constitute a lower bound on the maximum possible value of k, and a subset of them is shown to be optimal.     

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Counting colorful multi-dimensional trees

LetV be a disjoint union ofr finite setsV ₁,...,V _r (colors). A collectionT of subsets ofV iscolorful if each member ifT contains at most one point of each color. Ak-dimensional colorful tree is a colorful collectionT of subsets ofV, each of sizek+1, such that if we add toT all the colorful subsets ofV of sizek or less, we get aQ-acyclic simplicial complex _T We count (using the Binet-Cauchy theorem) thek-dimensional colorful trees onV (for allk), where each treeT is counted with weight . The result confirms, in a way, a formula suggested by Bolker. (fork-r–1). It extends, on one hand, a result of Kalai on weighted counting ofk-dimensional trees and, on the other hand, enumeration formulas for multi-partite (1-dimensional) trees. All these results are extensions of Cayley's celebrated treecounting formula, now 100 years old.     

Some remarks on (k−1)-critical subgraphs ofk-critical graphs

A graphG is said to bek-critical if it has chromatic numberk, but every proper subgraph ofG has a (k–1)-coloring. Gallai asked whether every largek-critical graph contains many (k–1)-critical subgraphs. We provide some information concerning this question and some related questions.