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

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