Combinatorics Seminar 2015

Speaker: John Goldwasser, West Virginia University

Date: Wed, Apr 08, 2015

Time: 14:05 - 15:05

Venue: Middle Meeting Room

Title: Maximum density of copies of perfect cycles in the $n$-cube and counting sequences


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 $J$ be a set of vertices in the $n$-cube, where $n$ is large. We show that the number of sub-$d$-cubes whose intersection with $J$ is an exact copy of $C_{2d}$ is equal to the number of sequences of $d$ distinct elements of an $n$-set which have a certain property. We have been able to solve the sequence problem for $d=4$, and we would have an inductive proof of our desired result if we were able to solve the sequence problem for $d=5$. This is an open problem. It turns out that $C_{2d}$ is a special subgraph of the $d$-cube, because its maximum density is the smallest maximum density of any configuration of vertices in the $d$-cube.

This is joint work with Ryan Hansen.