- 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)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Ron Holzman
- Project Mentor Area:
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.
