printable pdf
比利时vs摩洛哥足彩 ,
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

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