Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Reading

Steven Butler

UCSD Graduate Student

Cycle avoidance in hypercubes

Abstract:

Paul Erdos asked the following question: How many edges can a subgraph of the $n$-hypercube, $Q_n$, have that contains no $4$-cycle? The conjectured bound is $({1 \over 2}+o(1))e(Q_n)$ where $e(Q_n)$ denotes the number of edges of the hypercube. The best known result is due to Chung who also considered the more general question of $2k$ cycles where $k$ is even. More recently Alon, Radoicic, Sudakov, and Vondrak extended Chung's results to get Ramsey type results for $2k$ cycles where $k$ is odd. \vskip .1in \noindent In the talk we will review the developments of the problem and where it stands now.

Host:

June 23, 2005

1:00 PM

AP&M 6438

****************************