Ramsey’s Theorem implies that for any graph \(H\) there is a least integer \(r = r(H)\) such that if \(G\) is any graph of order at least \(r\) then either \(G\) or its complement contains \(H\) as a subgraph. For \(n<r\) and \(0 \leq e \leq \frac{1}{2}n(n-1)\), let \(f(e) =1\) {if every graph \(G\) of order \(n\) and size \(e\) is such that either \(G\) or \(\overline{G}\) contains \(H\),} and let \(f(e)=0\) {otherwise.} This associates with the pair \((H,n)\) a binary sequence \(S(H,n)\). By an interval of \(S(H,n)\) we mean a maximal string of equal terms. We show that there exist infinitely many pairs \((H,n)\) for which \(S(H,n)\) has seven intervals.

In this paper the existence of the \(12140\) non-isomorphic symmetric \((49,16,5)\) designs with an involutory homology (this is a special kind of involution acting on a design) is propagated. The automorphism groups are cyclic of orders \(2\), \(4\), \(8\), or \(10\). \(218\) designs are self-dual. The \(40\) designs with an automorphism group of order \(10\) were already given in [2]. A computer (IBM \(3090\)) was used for about \(36\) hours CPU time. According to [2,4] now there are known \(12146\) symmetric \((49,16,5)\) designs.

This paper deals with the joint distributions of some characteristics of the two-dimensional simple symmetric random walk in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, and west with equal probability.

In \(1974\), G. Chartrand and R.E. Pippert first defined locally connected and locally \(n\)-connected graphs and obtained some interesting results. In this paper we first extend these concepts to digraphs. We obtain generalizations of some results of Chartrand and Pippert and establish relationships between local connectedness and global connectedness in digraphs.

An infinite countable Steiner triple system is called universal if any countable Steiner triple system can be embedded into it. The main result of this paper is the proof of non-existence of a universal Steiner triple system.

The fact is proven by constructing a family \(\mathcal{S}\) of size \(2^{\omega}\) of infinite countable Steiner triple systems so that no finite Steiner triple system can be embedded into any of the systems from \(\mathcal{S}\) and no infinite countable Steiner triple system can be embedded into any two of the systems from \(\mathcal{S}\) (it follows that the systems from \(\mathcal{S}\) are pairwise non-isomorphic).

A Steiner triple system is called rigid if the only automorphism it admits is the trivial one — the identity. An additional result presented in this paper is a construction of a family of size \(2^{\omega}\) of pairwise non-isomorphic infinite countable rigid Steiner triple systems.

A graph \(G\) having a \(1\)-factor is called \(n\)-extendable if every matching of size \(n\) extends to a 1-factor. We show that
if \(G\) is a connected graph of order \(2p (p \geq 3)\), and g and n are integers, \(1 \leq n < q < p\), such that every induced connected subgraph of order \(2q\) is \(n\)-extendable, then \(G\) is n-extendable.

Certain graphs whose vertices are some collection of subsets of a fixed \(n\)-set, with edges determined by set intersection in some way, have long been conjectured to be Hamiltonian. We are particularly concerned with graphs whose vertex set consists of all subsets of a fixed size \(k\), with edges determined by empty intersection, on the one hand, and with bigraphs whose vertices are all subsets of either size \(k\) or size \(n-k\), with adjacency determined by set inclusion, on the other. In this note, we verify the conjecture for some classes of these graphs. In particular, we show how to derive a Hamiltonian cycle in such a bigraph from a Hamiltonian path in a quotient of a related graph of the first kind (based on empty intersection). We also use a recent generalization of the Chvatal-Erdos theorem to show that certain of these bigraphs are indeed Hamiltonian.

We determine the minimal number of queries sufficient to find an unknown integer \(x\) between \(1\) and \(n\) if at most one answer may be erroneous. The admissible form of query is: “Which one of the disjoint sets \(A_1, \ldots, A_k\) does \(x\) belong to?”

A \(\lambda\)-packing of pairs by quintuples of a \(v\)-set \(V\) is a family of \(5\)-subsets of \(V\) (called blocks) such that every \(2\)-subset of \(V\) occurs in at most \(\lambda\) blocks. The packing number is defined to be the maximum number of blocks in such a \(\lambda\)-packing. These numbers are determined here for \(\lambda \equiv 0 \mod 4\) and all integers \(v \geq 5\) with the exceptions of \((v, \lambda) \in \{(22, 16), (22, 36), (27, 16)\}\).

Recently, there has been substantial interest in the problem of the spectrum of possible support sizes of different families of BIB designs. In this paper, we first prove some theorems concerning the spectrum of any \(t\)-design with \(v = 2k\) and \(k = t + 1\), and then we study the spectrum of the case \(4-(10, 5, 6m)\) in more detail.