On Uniform Subset Graphs

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.