• This event has passed.

# Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles

## Thursday, December 15, 2022 @ 10:00 AM - 11:00 AM KST

Zoom ID: 224 221 2686 (ibsecopro)

### Speaker

Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht.

Our proof relies on a graph-theoretic analogue of homotopy equivalence, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex, and opens many further interesting questions.

## Details

Date:
Thursday, December 15, 2022
Time:
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:

## Venue

Zoom ID: 224 221 2686 (ibsecopro)

## Organizer

Joonkyung Lee (이준경)
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209