We prove that \(e(3,k+1,n) \geq 6n-13k\), where \(e(3,k+1,n)\) is the minimum number of edges in any triangle-free graph on \(n\) vertices with no independent set of size \(k+1\). To achieve this, we first characterize all such graphs with exactly \(e(3,k+1,n)\) edges for \(n \leq 3k\). These results yield some sharp lower bounds for the independence ratio for triangle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree \(4\) is shown to be \(\frac{4}{13}\). A slight improvement to the general upper bound for the classical Ramsey \(R(3,k)\) numbers is also obtained.

In this paper, we prove that for any \(n > 27363\), \(n \equiv 3\) modulo {6}, there exist a pair of orthogonal Steiner triple systems of order \(n\). Further, a pair of orthogonal Steiner triple systems of order \(n\) exist for all \(n \equiv 3\) modulo {6}, {3} \(< n \leq 27363\), with at most \(918\) possible exceptions. The proof of this result depends mainly on the construction of pairwise balanced designs having block sizes that are prime powers congruent to \(1\) modulo {6}, or \(15\) or \(27\). Some new examples are also constructed recursively by using conjugate orthogonal quasigroups.

We give a bijective proof for the identity \(S(n,k) \equiv \binom{n-j-1}{n-k} \pmod{2}\)
where \(j = \lfloor \frac{k}{2} \rfloor\) is the largest integer \(\leq\frac{k}{2}\) .

A bicover of pairs by quintuples of a \(v\)-set \(V\) is a family of 5-subsets of \(V\) (called blocks) with the property that every pair of distinct elements from \(V\) occurs in at least two blocks. If no other such bicover has fewer blocks, the bicover is said to be minimum, and the number of blocks in a minimum bicover is the covering number \(C_2(v, 5, 2)\), or simply \(C_2(v)\). It is well known that \(C_2(v) \geq \left \lceil \frac{v\left \lceil{(v-1)/2}\right \rceil}{5} \right \rceil = B_2(v)\), where \(\lceil x \rceil\) is the least integer not less than \(x\). It is shown here that if \(v\) is odd and \(v\not\equiv 3\) mod 10, \(v\not=9\) or 15,then \(C_2(v)=B(v)\).

For all nonnegative integers \(i,j\), let \(q(i, j)\) denote the number of all lattice paths in the plane from \((0,0)\) to \((i, j)\) with steps \((1,0)\), \((0,1)\), and \((1,1)\). In this paper, it is proved that

\[q(i_{n}p^{n}+…+i_0,j_np^n+…+j_0)\equiv(i_n,j_n)…q(i_0,j_0) \pmod{p}\]

where \(p\) is an odd prime and \(0 \leq i_k < p\), \(0 \leq j_k < p\). This relation implies a remarkable pattern to the divisibility of the array of numbers \(q(i, j)\).

Bauer and Tindell defined the graph invariant \(\wedge(G)\), for graphs \(G\) other than paths and the star \(K_{1,3}\), to be the least \(n\) for which \(G\) embeds in the \(n\)th iterated line graph of \(G\). They also proposed the problem of determining \(\wedge(T)\) for all trees \(T\). In this note, we completely solve this problem by showing that \(\wedge(T) = 3\) for any proper homeomorph \(T\) of \(K_{1,3}\) and that \(\wedge(T) = 2\) for all trees \(T\) which are neither paths nor homeomorphs of \(K_{1,3}\).

In a previous paper, all non-isomorphic decomposable \(3-(12,6,4)\) designs without repeated blocks were determined. These results are extended here by allowing repeated blocks. Under this condition, there are \(26\) non-isomorphic decomposable \(3-(12,6,4)\) designs, of which \(14\) have repeated blocks. Key blocks and point permutations for models of these designs are given, along with descriptions of their automorphism groups.

We extend the definition of edge-cordial graphs due to Ng and Lee for graphs on \(4k\), \(4k+1\), and \(4k+3\) vertices to include graphs on \(4k+2\) vertices, and show that, in fact, all graphs without isolated vertices are edge-cordial. Ng and Lee conjectured that all graphs on \(4k\), \(4k+1\), or \(4k+3\) vertices are edge-cordial.

We define the semibandwidth of a bipartite graph (whose bipartition is specified), which is a bipartite analogue of the bandwidth of a graph, and develop some of its properties. The motivation for this concept comes from the question of transforming a matrix by row and column permutations to as close to triangular form as possible.