Student: | Stanislav Kucera |
---|---|

Office: | 442 |

School: | Faculty of Mathematics and Physics, Charles University in Prague |

E-mail: | skucera@reu.dimacs.rutgers.edu |

Project: | Upper bounding Burning number |

We try to prove that burning number of any graph on $n$ vertices is at most $\sqrt{n}$.

I work on this project mainly with Jakub Pekárek as part of the czech team, namely Martin Böhm, Mark Karpilovskij, Karel Král, Veronika Slívová and Martin Töpfer.- Week 1:
- Trying several approaches of graph induction and polynomial algorithm designs.
- Week 2:
- Still trying to prove the conjecture. One of induction condition improved.
- Week 3:
- Trying to find equivalent or harder problems, which could be easier to analyse.
- Week 4:
- We are trying to improve an algorithm using the euclidian cycle.
- Week 5:
- After our previous approach did not end up where we wanted, we start focusing on existential proves (for example probabilistic method) rather than trying to come up with an algorithm.
- Week 6:
- With help of Martin Bohm, we have discovered a new property of the smallest counter-example, which says that the longest connected part of the graph without any vertices of degree bigger than two is atmost $2\sqrt{n}$ long.
- Week 7:
- We are trying to further restrict potential counter-example to finally get to the contradiction.

- My Mentor