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
****************************