| Name: | Andrej Dedik |
|---|---|
| Email: | [lastname][firstname]-[at]-[gmail][dot][com] |
| Office: | CoRE 450 |
| Home Institution: | Charles University |
| Project: | A Graph Game from Extremal Combinatorics |
About My Project
The game mentioned in the project is played by two players on an intially empty discrete graph. One player tries to force induced subgraph (which is given at the start of the game) by choosing stable sets, into which the other player has to draw edges. The forcing (player one) player wins if he forces second player to complete the induced subgraph. Other player wins if forcing player fails to do so.
The question which pops up is: Is it always possible to force graph on some given number of vertices? This question has been answered, and as it turns out, the answer is yes - for each graph there is such a number of vertices, such that forcing player has strategy to force the graph in question.
What we do not know though, is what this number is for most of the known graphs. We know, that for complete graphs the number is (for obvious reasons) Ramsey's number, but not much else is known. There is an lower and upper bound, but they are really quite far from each other. Hence our goal is to get a deeper understanding of this problem and investigate if these bounds could be squeezed together more tightly.
Research Log
Week 1
As one could except, week one contained a lot of moving in, good deal of acclimatization, quite a lot bureaucracy and not sufficient amount of research. I've managed to read some papers about the problem [1] provided by my mentor and I should have been all set up for the next week.
Week 2
Me and my research partner met with our mentor for the first time. We all made clear, that we are on the save wavelength and discussed the possible paths our research could take and ruled out ones we should take not.
So for the next few days we were looking around the possible variants of the game, trying to see if some interesting ideas would pop up, as well as proving some non-trivial cases for both variants of the game. I've found several papers about induced subgraphs in extremal theory, so I will take a look at them and see if any of them might be of use to us.
There was also a second meeting with our mentor, where we've discussed possible ways to research our topic, such as researching behavior of the game, once we relax the original statement of the game from graph to family of graphs, or trying to make a device for proving small graphs (like stars for instance) as well as probabilistic approach to the game.
This week presented us with a lot of questions and, luckily, with some answers, so there is some work done and piles of work to do. Next week I want to delve into one of the proposed variants of the game.
Week 3
New week, new challenges (well, not so new we found out about them last week) and hopefully - new answers. My coworker had been very proficient with using general knowledge about triangle free graphs and proved that we can force either complete graph or complete bipartite graph on arbitrary number of vertices.
Another nice result we have gotten is that we can force paths in exponential time for fixed k. From this fact we have been able to show that we can force cycles of arbitrary size for k equals three. Both proofs are quite simple and elegant, but one works for all k's while the other one works for only k of size three.
So the question for next week is probably going to be about what can we force out of paths. The main suspect - trees.
Week 4
This week is going to be quite short, since we went to Bell Labs on monday, the trip was great, seeing the workplace of many great minds and visiting anechoic chamber was worth at the expense of losing one workday (there was also pizza).
Despite the lack of one working day, the week was quite progressive and quite regressive as well - the lower bound does not work as we intended and hence we need to generalize the result for that one particular case. On the other hand, we have found a way to force trees for k equals three in linear time. We will try to generalize this approach for the rest of the k's. If proven correct, we suspect that it might be possible to force cycles in polynomial, or maybe even linear time
Towards the end of the week, my coworker came up with briliant idea for paths, which does not work yet but it looks very promising.
Week 5
Heureka! The construction for paths works and therefore, we can now force paths in polynomial time. Not only that, but this result allows us to force cycles of arbitrary length for any given k in polynomial time.
We have missed a fact, that the construction for cycles does not work for cycle of length four. Hence our main goal right now is to show that it is indeed possible to force such cycle in polynomial time.
Our mentor is satisfied (hopefully) with our answers and so proposed more, significantly more difficult, questions to think about.
Also, I am starting to work on the draft of our paper and will let my coworker to think about proposed problems.
Week 6
Thankfully, we now have the proof for cycle of lenght four, but it is not as neat as for the other cycles (but quite neat nontheless).
To be quite honest, I don't think I can contribute to our research much more, since the questions we're trying to solve from this point on are quite difficult (essentialy answering some of these questions would be significant progress towards proving Erdos-Hajal conjecture [Or atleast I've been told so {but I might be taking this out of context <So sorry Honza>}]). Best I can do is to start working on final presentation, the paper and maybe a poster.
There was a seminar on scientific writing - the seminar was quite nice and funny, but most of all informative. Not that I have no idea how to write scientific papers, but it is nice when presentation tells you that what you have been doing for last three working days is the way is the way it is supposed to be done... #HumbleBrag
Presentations
Additional Information
- Mentor:
- Research Partner:
Acknowledgments
- This research is part of a project that has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 823748.