This paper addresses the following questions. In any graph $G$ with at least $\alpha (\genfrac{}{}{0ex}{}{n}{2})$ edges, how large of an induced subgraph $H$ can we guarantee the existence of with minimum degree $\delta (H)\ge \lfloor \alpha |V(H)|\rfloor$? In any graph $G$ with at least $\alpha (\genfrac{}{}{0ex}{}{n}{2})–f(n)$ edges, where $f(n)$ is an increasing function of $n$, how large of an induced subgraph $H$ can we guarantee the existence of containing at least $\alpha (\genfrac{}{}{0ex}{}{|V(H)|}{2})$ edges? In any graph $G$ with at least $\alpha n^2$ edges, how large of an induced subgraph $H$ can we guarantee the existence of with at least $\alpha |V(H){|}^2+\mathrm{\Omega }(n)$ edges? For $\alpha =1–\frac{1}{r}$, for $r=2,3,\dots$, the answer is zero since if $G$ is a complete $r$-partite graph, no subgraph $H$ of $G$ has more than $\alpha |V(H){|}^2$ edges. However, we show that for all admissible $\alpha$ except these, the answer is $\mathrm{\Omega }(n)$. In any graph $G$ with minimum degree $\delta (G)\ge \alpha n–f(n)$, where $f(n)=o(n)$, how large of an induced subgraph $H$ can we guarantee the existence of with minimum degree $\delta (H)\ge \mathrm{\Omega }|V(H)|$?

From any projective plane $\mathrm{\Pi }$ of even order $n$ with an oval ($(n+2)$-arc), a Hadamard $3$-design on $n^2$ points can be defined using a well-known construction. If $\mathrm{\Pi }$ is Desarguesian with $n=2^m$ and the oval is regular (a conic plus nucleus) then it is shown that the binary code of the Hadamard $3$-design contains a copy of the first-order Reed-Muller code of length $2^{2m}$.

The $geodeticcover$ of a graph $G=(V,E)$ is a set $C\subseteq V$ such that any vertex not in $C$ is on some shortest path between two vertices of $C$. A minimum geodetic cover is called a $geodeticbasis$, and the size of a geodetic basis is called the $geodeticnumber$. Recently, Harary, Loukakis, and Tsouros announced that finding the geodetic number of a graph is NP-Complete. In this paper, we prove a stronger result, namely that the problem remains NP-Complete even when restricted to chordal graphs. We also show that the problem of computing the geodetic number for split graphs is solvable in polynomial time.

We exhibit a self-conjugate self-orthogonal diagonal Latin square of order $25$.

We consider the problem of scheduling $n$ independent tasks on a single processor with generalized due dates. The due dates are given according to positions at which jobs are completed,rather than specified by the jobs.We show that the following problems are NP-Complete,$1|\text{prec},p_j=1|\sum w_j{U}_j$,$1|\text{chain},p_j=1|\sum w_j{U}_j$,$1|\text{prec},p_j=1|\sum w_j{T}_j$, and $1|\text{chain},p_j=1|\sum w_j{T}_j$.With the removal of precedence constraints, we prove that
the two problems,$1|p_j=1|\sum w_j{U}_j$ and $1|p_j=1|\sum w_j{T}_j$,
are polynomially solvable.

The paper studies linear block codes and syndrome functions built by the greedy loop transversal algorithm. The syndrome functions in the binary white-noise case are generalizations of the logarithm, exhibiting curious fractal properties. The codes in the binary white-noise case coincide with lexicodes; their dimensions are listed for channel lengths up to sixty, and up to three hundred for double errors. In the ternary double-error case, record-breaking codes of lengths $43$ to $68$ are constructed.

Suppose that a finite group $G$ acts on two sets $X$ and $Y$, and that $FX$ and $FY$ are the natural permutation modules for a field $F$. We examine conditions which imply that $FX$ can be embedded in $FY$, in other words that $(\ast )$: There is an injective $G$-map $FX\to FY$. For primitive groups we show that $(\ast )$ holds if the stabilizer of a point in $Y$ has a `maximally overlapping’ orbit on $X$. For groups of rank three, we show that $(\ast )$ holds unless a specific divisibility condition on the eigenvalues of an orbital matrix of $G$ is satisfied. Both results are obtained by constructing suitable incidence geometries.

A Latin square $(S,\ast )$ is said to be $(3,2,1)$-conjugate-orthogonal if $x\ast y=z\ast w$, $x{\ast }_{321}y$, $z{\ast }_{321}w$ imply $x=z$ and $y=w$, for all $x,y,z,w\in S$, where $x_3{\ast }_{321}{x}_2=x_1$ if and only if $x_1\ast x_2=x_3$. Such a Latin square is said to be \emph{holey}($(3,2,1)$-HCOLS for short) if it has disjoint and spanning holes corresponding to missing sub-Latin squares.Let $(3,2,1)$-HCOLS$(h^n)$ denote a $(3,2,1)$-HCOLS of order $hn$ with $n$ holes of equal size $h$. We show that, for any $h\ge 1$, a $(3,2,1)$-HCOLS$(h^n)$ exists if and only if $n\ge 4$, except $(n,h)=(6,1)$ and except possibly $(n,h)=(6,13)$. In addition, we show that a $(3,2,1)$-HCOLS with $n$ holes of size $2$
and one hole of size $3$ exists if and only if $n\ge 4$, except for $n=4$ and except possibly $n=17,18,19,21,22$ and $23$. Let $(3,2,1)$-{ICOILS}$(v,k)$ denote an idempotent $(3,2,1)$-COLS of order $v$ with a hole of size $k$. We provide $15$ new $(3,2,1)$-ICOILS$(v,k)$, where $k=2,3,$ or $5$.

A balanced part ternary design (BPTD) is a balanced ternary design (BTD) with a specified number of blocks, say $b_2$, each having repeated elements. We prove some necessary conditions on $b_2$ and show the existence of some particular BPTDs. We also give constructions of infinite families of BPTDs with $b_1=0$, including families of ternary $t$-designs with $t\ge 3$.

We prove a very natural generalization of the Borsuk-Ulam antipodal theorem and deduce from it, in a very straightforward way, the celebrated result of Alon [1] on splitting necklaces. Alon’s result states that $t(k-1)$ is an upper bound on the number of cutpoints of an opened $t$-colored necklace such that the segments obtained can be used to partition the set of vertices of the necklace into $k$ subsets with the property that every color is represented by the same number of vertices in any element of the partition. The proof of our generalization of the Borsuk-Ulam theorem uses a result from algebraic topology as a starting point and is otherwise purely combinatorial.