Szemerédi’s density theorem extends van der Waerden’s theorem by saying that for any \(k\) and \(c\), \(0 < c < 1\), there exists an integer \(n_0 = n_0(k, c)\) such that if \(n > n_0\) and \(S\) is a subset of \(\{1, 2, \ldots, n\}\) of size at least \(cn\) then \(S\) contains an arithmetic progression of length \(k\). A “second order density” result of Frankl, Graham, and Rödl guarantees that \(S\) contains a positive fraction of all \(k\)-term arithmetic progressions. In this paper, we prove the analogous result for the Gallai-Witt theorem, a multi-dimensional version of van der Waerden’s theorem.

This paper discusses the chromatic number of the products of \(n+1\) -chromatic hypergraphs. The following two results are proved:
Suppose \(G\) and \(H\) are \(n+ 1\) -chromatic hypergraphs such that each of \(G\) and \(H\) contains a complete sub-hypergraph of order n and each of \(G\)    and \(H\) contains a vertex critical \(n + 1\)-chromatic sub-hypergraph which has non-empty intersection with the corresponding complete sub-hypergraph of order \(n\). Then the product \(G \times H\)is of chromatic number \(n + 1\).
Suppose \(G\) is an \(n+ 1\)-chromatic hypergraph such that each vertex of \(G\) is contained in a complete sub-hypergraph of order n. Then for any \(n + 1\)-chromatic hypergraph \(H\), \(G \times H \) is an \(n + 1\)-chromatic hypergraph.

A set \(S\) is called \(k\)-multiple-free if \(S \cap kS = \emptyset\), where \(kS = \{ks : s \in S\}\). Let \(N_n = \{1, 2, \ldots, n\}\). A \(k\)-multiple-free set \(M\) is maximal in \(N_n\) if for any \(k\)-multiple-free set \(A\), \(M \subseteq A \subseteq N_n\) implies \(M = A\). Let

\[A(n, k) = \{|M| : M \subseteq N_n is maximal k -multiple-free\}\].

Formulae of \(\lambda(n,k)= \max \Lambda(n, k)\) and \(\mu(n, k) = \min \Lambda(n, k)\) are given. Also, the condition for \(\mu(n, k) = \Lambda(n, k)\) is characterized.

We enumerate various families of planar lattice paths consisting of unit steps in directions \( {N}\), \({S}\), \({E}\), or \({W}\), which do not cross the \(x\)-axis or both \(x\)- and \(y\)-axes. The proofs are purely combinatorial throughout, using either reflections or bijections between these \({NSEW}\)-paths and linear \({NS}\)-paths. We also consider other dimension-changing bijections.

Let \(x_1, x_2, \ldots, x_v\) be commuting indeterminates over the integers. We say an \(v \times v \times v \ldots \times v \) n-dimensional matrix is a proper \(v\)-dimensional orthogonal design of order \(v\) and type \((s_1, s_2, \ldots, s_r)\) (written \(\mathrm{OD}^n(s_1, s_2, \ldots, s_r)\)) on the indeterminates \(x_1, x_2, \ldots, x_r\) if every 2-dimensional axis-normal submatrix is an \(\mathrm{OD} (s_1, s_2, \ldots, s_r)\) of order \(v\) on the indeterminates \(x_1, x_2, \ldots, x_r\). Constructions for proper \(\mathrm{OD}^n(1^2)\) of order 2 and \(\mathrm{OD}^n(1^4)\) of order 4 are given in J. Seberry (1980) and J. Hammer and J. Seberry (1979, 1981a), respectively. This paper contains simple constructions for proper \(\mathrm{OD}^n(1^{2})\), \(\mathrm{OD}^n(1^{4})\), and \(\mathrm{OD}^n(1^{ 8})\) of orders 2, 4, and 8, respectively. Prior to this paper no proper higher dimensional OD on more than 4 indeterminates was known.

Bondy and Fan recently conjectured that if we associate non-negative real weights to the edges of a graph so that the sum of the edge weights is \(W\), then the graph contains a path whose weight is at least \(\frac{2W}{n}\). We prove this conjecture.

Let \(H(V, E)\) be an \(r\)-uniform hypergraph. Let \(A \subset V\) be a subset of vertices and define \(\deg_H(A) = |\{e \in E : A \subset e\}|\).

We say that \(H\) is \((k, m)\)-divisible if for every \(k\)-subset \(A\) of  \(V(H)\), \(\deg_H(A) \equiv 0 \pmod{m}\). (We assume that \(1 \leq k < r\)).

Given positive integers \(r \geq 2\), \(k \geq 1\) and \(q\) a prime power, we prove that if \(H\) is an \(r\)-uniform hypergraph and \(|E| > (q-1) \binom{\mid V \mid}{k} \), then \(H\) contains a nontrivial subhypergraph \(F\) which is \((k, q)\)-divisible.