Filip Cermak's REU 2020 Web Page

Name:	Filip Cermak
Email:	filip.cermak2-[at]-[gmail][dot][com]
Mentor:	Bhargav Narayanan
Home Institution:	Charles University
Project:	Coloring problems in graph theory

---

Research Log

Week 1

Before and during the first week, I was thinking about the two coloring problem and solved it by induction. Then I was getting into the problematic a little bit more.

Week 2

On Monday, we had our presentation, it was the first time I saw other participants so it was great to realize that a lot of people work on interesting topics during this REU program. On Tuesday we were listening to the rest of presentations

I was trying to find out counterexample for small number of vertices. I wrote a python program which tries to bruteforce the solution but it was unsuccesful. On Thursday we met with the rest of our team and we were trying to think up the counterexample together. We also discussed two color problem and talked little bit about infinite maze problem.

I continued inventing the counter example and read our mentor code about that.On Friday there was a presentation about AI Tools for Creative Work by Lydia Chilton.

Week 3

We were trying to understand out mentor's code in more detail I was learning more about mathematica programming language.

At the end of the week I realized how the code works

We had a talk about two color problem, about out solutions and also about calculation for three and more colors. We have started considering differences of functional values because they better capture the propertities of a function.

Week 4

I converted our mentor's counterexample from non-graph to graph counterexample.

We also made up counterexample for all blue not just first blue event.

Then we also discussed again the notes from previous week and we tried to understand the ideas to describe the problem with functions which describe the probability of every state.

We also convert the different functional values of counterexample fucntion to values from 1 to 3 to be more easy to see how the counterexample works.

Week 5

This week we tried to find counter example of one increasing functions that contradicts our assumption. In other words convert functions changing in time into one.

We found out a lot of new functions which could be better to convert into one function. In the first half of a week we invented a lot of techniques how to convert the functions. Nevertheless none of them works

But by the end of the week we look more into it and analyze it more we figure out a new technique which led to the one function counterexample.

Week 6

We started discussing convexity as one of the key properties of exponential function and try to figure out it we are able to prove something about it.

We use coupling as in the proof for two to prove it also for three colors. We figured out that if there is enough blue vertices and the function is convex (even function changing in time) then it works.

But it is still not clear if it can be somehow generalized into a proof or there is counterexample because we can get into some states where there are no enough blue vertices.

Week 7 && Week 8

We have been discussing convex counterexamples, trying to figure out how it works and we made some non-graph counter examples and in the end also graph ones. The functions functions still needs a huge jump at some "treshold" so it still not clear how it works for exponential.

Week 9

We were preparing final presentation , trying to finalize details and we were making the paper.