REU Project
- Antipodal paths in 2-colorings of hypercubes
- Project Year: 2020
- REU Student (s): Tomas Hons | Charles University (Prague, Czech Republic) | Marian Poljak | Charles University (Prague, Czech Republic) | Tung Anh Vu | Charles University (Prague, Czech Republic)
- Project Mentor (s) : Ron Holzman - Mathematics, Princeton University
- Project Abstract:
Feder and Subi conjectured that for any 2-coloring of edges of the hypercube Qn, there always exists a pair of antipodal vertices connected by a shortest path which changes color at most once. Leader and Long proved that there always exists a path between antipodal vertices with at most n/2 changes and Dvorak improved this bound to (3/8+o(1))n. We give some partial results which may lead to further improvements of Dvorak's upper bound.