\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf J. Robert Johnson }
%
%
\medskip
\noindent
%
%
{\bf An Inductive Construction for Hamilton Cycles in Kneser Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
The Kneser graph $K(n,r)$ has as vertices all $r$-subsets of an
$n$-set with two vertices adjacent if the corresponding subsets are
disjoint. It is conjectured that, except for $K(5,2)$, these graphs are Hamiltonian for all $n\geq 2r+1$. In this note we describe an inductive construction which relates Hamiltonicity of $K(2r+2s,r)$ to Hamiltonicity of $K(2r'+s,r')$. This shows
(among other things) that Hamiltonicity of $K(2r+1,r)$ for all $3\leq r\leq k$ implies Hamiltonicity of $K(2r+2,r)$ for all $r\leq 2k+1$.
Applying this result extends the range of values for which Hamiltonicity of $K(n,r)$ is known.
Another consequence is that certain families of Kneser graphs ($K(\frac{27}{13}r,r)$ for instance) contain infinitely many Hamiltonian graphs.
\end{document}