General Information

---

Project Description

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.

---

Weekly Log

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.

---

Presentations

• First Presentation
• Second Presentation

---

Additional Information

• My Mentor
  • Dr. Eric Allender