General Information

Aneta Stastna
Student: Aneta Šťastná
Office: 448
School: Charles University
E-mail: aneta.stastna@email.cz
  • alternative formulation of Erdös-Faber-Lovász conjecture

  • Project Description

    I am part of Czech group consisting of Martin Hora, Václav Končický, Michael Skotnica, Ondřej Šplíchal, Jakub Tětek Václav Končický Peter Korcsok and myself. Our group will have multiple projects to solve, some of them we have already chosen and searched information about. We don't have a settled name and short description of the problems yet, so I'll add them later.

    Weekly Log

    Week 1 (29.5. - 3.6.):

    During Wednesday morning I attended the initial talks, got to know better some of the other participants and in the afternoon we discussed unsolved problems which we could work on.

    On Thursday we have discussed and chosen some topics for the bridge workshops. I have decided to cooperate with Ondra Šplíchal on Erdös-Faber-Lovász conjecture, because Ondra came up with some pretty intuitive alternative formulation. I found some literature and started reading unpublished proof of the conjecture from January 2017 to understand it. If there is a problem with the proof, we could correct it or just translate it into our formulation to make it more understandable. I also initialized this page.

    Week 2 (4.6. - 10.6.):

    I have been reading the unpublished article with proof of the conjecture. I understood what the authors ment to do and programmed their algorithm in order to be able to see what happens with the color matrix step-by-step. There is at least one bad point in the algorithm where we are taking color from a set which might be empty. I'll just run the program on some random graphs to get an example where it doesn't work.

    On Wednesday we had a meeting with our mentor and he slightly introduced us to two more problems to solve. However, we didn't get enough information to start working or reading anything, so I continued the work on the original problem.

    One of the ideas used in the unpublished proof is using a symmetric latin square to color the graph. Together with Ondra we discovered that there is connection between symmetric latin squares and tetrises. Also, Ondra made up an algorithm to color the minimal instance of graph which satisfies presumptions of the EFL conjecture and I have formulated that in a pseudocode. We might use coloring of the minimal instance to color all other instances.

    Week 3 (11.6. - 17.6):

    I started reading an article about connection of b-coloring of graphs and EFL conjecture. What interests me is that the article also uses the symmetric latin squares. Simultaneously, Ondra started thinking about relation between fields and symmetric latin squares.

    On Wednesday there had been a bridge workshop on Ramsey numbers. On Thursday we had a meeting with our mentor and on Friday has been a culture day. I finished reading the article about b-coloring.

    Week 4 (18.6. - 24.6.):

    On Monday I have been reading one article about cryptography from our mentor and later that day we have met with him. During this week I have studied a summary article about the EFL conjecture and started writing article about different approaches to EFL and how are they all connected to tetrises. On Tuesday there has been a seminar about math around gravity. On Wednesday we visited the IBM Watson research center.

    Week 5 (25.6. - 1.7.):

    I have sent an email to the authors of the b-coloring article, as there had been a stronger result than their in an unpublished article, but it is wrong. Ondra came up with conjecture stronger than EFL and I thoght of an counterexample. I continued work on the article about different approaches to EFL and came up with my own conjecture.

    Week 6 (2.7. - 8.7.):
    On Monday the scientific writing workshop took place. I started reading article with newer results with b-coloring. On Tuesday I have been leading a bridge workshop about aproximation and online algorithms. In the afternoon I have discovered that we can prove the whole theorem about b-coloring of one special type of graph, which has already been proven by Lin and Chang. We have proven this using tetrises.

    On Wednesday I tried to prove my conjecture. I believe that it holds but I start wondering if it is possible to prove it using the presumptions. On Thursday there has been a seminar about modelling changes of blood pressure. During the rest of the week I started adding tetris definitions and results to our article.

    Week 7 (8.7. - 14.7.):


    Additional Information