General Information

My project

Suppose we are given 2-edge-coloring of a hypercube Q_n that is antipodal, ie. opposite edges are assigned with different color. Is it true that exists a monochromatic path connecting two antipodal vertices? We tried to aswer this question.

Weekly log

Week 1

The first week was a bit slow from my part. But we have managed to make a great presentation (even stylistically). The next week the real work will begin. Our team has agreed on regular meetings in Prague and firstly we start with deep exploration of small hypercubes e.g. Q_4 (similar to what Vojtěch Dvořák did).

Week 2

We had two meeting of our team. At the first one, we discussed thing more in general perpestive and were maily exploring the field without any concrete work.

At the second week, we start off with solving loads of various simple questions 'just to get into that'. It was probably also not extremely productive, but it was great to actually do something more than just reading papers.

Week 3

This week we continued our work on small cubes and we have our first small results. The proofs were primarily based on computer calculations while we tried to justify the results from human point of view (with partial success).

Week 4

On week 4 we again work with small cubes (dimension 4 and 5) but we also aim on more general question and we has a few results there. But to our disappointment we discovered that those statements was proved before.

Week 5

Starting the second half of the program, we tried to use various kind of inductive arguments to limit the maximum average number of switches among the antipodal paths with the least number of switches (ie. the maximum is over all coloring, the average is over all antipodal pair, while the minimum number of switches is over all antipodal path connecting a fixed pair of antipodal vertices). However, none of the approaches yield any result nor important insight.

Week 6

We tried to focus at the particular case of Q_5 as the general result for all hypercubes seems intractable (knowing that we are supposed to conclude our finding quite soon). We achieved some partial result assuming some additional restiction on given coloring.

Week 7

Some further partial results for Q_5 case were established, while we also obtained a finer grained description of boundary cases of Q_4 coloring (ie. for the coloring which attain the maximum switch number).

Week 8

This week we started writing our paper while polishing proofs of some earlier statements.

Week 9

The last week we finished writting of the paper and prepared a presentation for the final meeting.

Presentations

• Presentation about our group's topic given in the first week: [PDF file] [source code].
• Final presentation about our group's results: [PDF file] [source code].

Acknowledgement

This work was carried out while the author Tomáš Hons was a participant in the 2020 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.