Combinatorics Seminar 2015

Speaker: Zongchen Chen (陳宗晨), Shanghai Jiao Tong University

Date: Wed, May 27, 2015

Time: 13:40 - 14:40

Venue: Middle Meeting Room

Title: Maximum density of perfect cycles in the hypercube


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 -- a $2d$-cycle induced by $d$ pairs of vertices at distance $d$. Let $J$ be a set of vertices in the $n$-cube, where $n$ is large. We try to determine the maximum density of good sub-$d$-cubes whose intersection with $J$ is precisely a copy of $C_{2d}$. To do this, we first check the maximum local density of good sub-4-cubes that containing a particular vertex $v$.

Assume $A(d,n)$ is a family of strings from an $n$-character alphabet and each string contains exactly $d$ distinct characters. A family $A(d,n)$ is called good if it satisfies the following property: for any two strings $x$, $y$ in $A(d,n)$, if $T$ is an end-segment (prefix or suffix) of $x$ and each character of $T$ is also in $y$, then $T$ is an end-segment of $y$. We can prove that a good family $A(d,n)$ contains at most $2(n/d)^d$ strings.

For the case $v \in J$, we show that the local density of good sub-$d$-cubes containing $v$ is no more than $d!/d^d$ by transforming good sub-$d$-cubes into a good family $A(d,n)$ of strings. This implies the maximum density of good sub-4-cubes is $4!/4^4$.

Slides: View slides