General Information

My project

Weekly log

Week 1

We were already in touch with our mentor before REU officially started. He explained the problem to us, which gave us more time to read all the related papers and have a quicker start. During the first week, we met and created a professionally looking presentation, which we then presented to other REU students and mentors. Our team has agreed on regular meetings in Prague. We work as a group of three people, therefore the following descriptions might be either copied or at least resembling the notes of my teammates :)

Week 2

Still finding out how other researchers approached the problem. We also had two meetings of our team. At the first one, we discussed the topic from a general perspective.

For the second meeting, in order to get into the topic, we tried out to calculate various hypercube-related quantities, which gave us an idea about how the hypercubes behave and in which representations we should think of them for higher dimensions.

Week 3

We tried to get a better understanding of the average number of switches between all pairs of antipodal vertices in a random (not necessarily antipodal) coloring. We devised a brute-force algorithm to enumerate the colorings for us.

Week 4

Definition: a switch vector u of a fixed coloring of a Q_n as a vector of length 2^{n-1} where u_i denotes the minimum number of switches between i and its antipodal vertex i'. We define a function f: ℕ → ℝ as the maximum ratio between the sum of the entries of a switch vector and 2^n over all colorings of Q_n. To list a few values, we know f(1) = 0, f(2) = 1, f(3) = 1. Computationally we know that f(4) = 1.25. We conjecture that f(5) = 1.25 also. We have a proof that function f is non decreasing.

Week 5

We tried to examine a hypercube of dimension n by splitting it into subcubes of dimension n-1 in n different ways by fixing each coordinate. It seems to be a stronger starting point than what we previously worked with, but unfortunately this did not yield any new results.

We also tried to give a bound on combining two switch vectors of a hypercube of dimension n-1 into a switch vector of a hypercube of dimension n. There is a trivial upper bound where each entry from the resulting switch vector is at most min(a_i,b_i)+1. This also did not yield any new knowledge.

Presentations

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

References

Acknowledgement

This work was carried out while the author Marian Poljak 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.