Combinatorics Seminar 2015

Speaker: John Goldwasser, West Virginia University

Date: Wed, Apr 15, 2015

Time: 15:30 - 16:30

Venue: Room 1202

Title: Maximum density of copies of perfect cycles in the $n$-cube, sequences, and (0,1)-matrices


The $n$-cube is the graph whose vertex set is the set of all binary $n$-tuples, with two vertices adjacent if and only if they differ in precisely one coordinate. Let $C_{2d}$ denote the vertices of a ``perfect'' $2d$-cycle in a $d$-cube -- an induced $2d$-cycle with $d$ pairs of vertices at distance $d$. Let $S$ be a set of vertices in the $n$-cube, where $n$ is large. We show that the maximum, over all sets $S$ of the vertices, of the number of sub-$d$-cubes whose intersection with $S$ is an exact copy of $C_{2d}$ is equal to the maximum number of sequences of $d$ distinct elements of an $n$-set which have a certain property. We have been able to maximize the number of sequences when $d=4$ by finding which $m \times m$ (0,1) matrix has the most $2\times 2$ sub-matrices which have precisely one 1 in each row and column. We have not been able to prove our conjecture about the maximum number of sequences when $d>4$. It turns out that $C_{2d}$ is a special subgraph of the $d$-cube, because its maximum density in a large $n$-cube is the smallest maximum density of any configuration of vertices in the $d$-cube. Joint work with Ryan Hansen.

This is a sequel to my talk on April 8 in this combinatorics seminar. We will make the talk accessible to undergraduate students and to those who did not attend my first talk.