General Information

---

Project Description

Our project is to research relatively new property of graphs called burning number. Burning number is a concept arising from analysis of social networks, especially from study of information propagation through media. Abstracted version of this model can also describe other spreading processes, such as spreading of fire or disease.

The simplest definition of a burning number of a graph is the shortest sequence of vertices, such that this sequence dominates the whole graph with various radius of dominance. The radius of dominance increases from 0 up to length of the sequence - 1.

The currently open hypothesis is that the burning number of any connected graph is at most $\sqrt{n}$. Main focus of our research on REU is to prove this conjecture. Our alternative goal is to at provide closer estimates from general or specific graphs. We also expect to encounter numerous corollaries and related problems that we might choose to research.

I work on this project mainly with Stanislav Kučera as part of the czech team, namely Martin Böhm, Mark Karpilovskij, Karel Král, Veronika Slívová and Martin Töpfer.

---

Week 1:

In our first week we focused mainly on gaining insight into basic properties of burning number and conjecture we are attempting to prove.
We studies materials [1,2,3], described various properties of possible counter-examples to main conjecture.
We developed new simple proof of previously known upper bound $\sqrt{2n}$ for burning number of general graphs. Our study also lead to development of new approach using dominating sets improving upon results of A. Bonato, J. Janssen [2] and reaching the same result. Although these results can be improved, these improvements are negligible in view of our goal, and we believe that neither of the two approaches allows significant improvement leading to proof of conjecture.

Week 2

In our second week we focused mainly in various strategies in our attempt to identify specific examples of hard cases in reaching goal conjecture.
Our observations suggest that existence of any dynamic algorithm is highly unlikely.
One of our other minor accomplishments this week has been implementation of computer search for counter-examples which yielded specific graphs that do not allow usage of greedy algorithms. It is nevertheless unclear, whether these structures is consistent with previously described properties of counter-examples.
Using this knowledge we designed simple algorithm for burning graph using at most $\sqrt{n}$, such that we are unable to produce any graph structure where algorithm fails using computer search.
Based on these result we started construction of burning strategies for wide varieties of graphs depending on their dominant structural features.

Week 3

Our focus this week was mainly in finding equivalent or related problems to burning number.
Some of our time was used for deeper exploration of structural manipulations of graphs that guarantee invariance of change of burning properties. One of our goal of this exploration of finding properties that extend to substructures and super-graphs.
We explored directed and contracting variations and made some observations connected to our hypothesis.
We formulated linear program for burning number. We focused on gaining combinatorial information about dual problems and possible existence of primal-dual algorithm.
We also managed to introduce minor improvements into our knowledge of minimal counter-examples and previously studied burning strategies.

Week 4

Based on some of our gathered knowledge we made several observations regarding necessary structural properties of graphs. With these we can now guarantee existence of efficient burning steps. One of our next goals is to elaborate on these results and construct burning strategy that would improve upon all so far proven upper bounds.
To pursue our previously mentioned goal, we revisited some of our previous results and construction used in our current sketch of strategy. We are optimistic that our current approaches will eventually yield interesting results and we hope that our constructions will improve the best known published result $1.309\sqrt{n}+3$ (given by S. Bessy and D. Rautenbach [3]), possibly up to value $1.155\sqrt{n}+c$ (according to our current estimate). After dealing with some core issues is seems that universal application of our results may not be capable of remaining efficient enough to reach such value.
The last few day of the week we were working more closely with our colleague Mark on problem of simplicial complex embedding and reached some interesting and exciting results. This work needs finishing, during the next week to be discussed with our Czech advisor for geometry. Because of that we invested less time into our main project and might need to continue in this manner during the next week.

Week 5

In the fifth week we kept focusing part of our time into geometry problem rather than burning number conjecture.
Our constructions from previous week proved to be much more complicated to finish than we presumed, especially due to immense amount of technical details. Since the construction can lead to mere improvement of current bound rather than proving our target conjecture, we shifted our main focus to different existential approaches. We now believe that constructive approach to the conjecture is inherently harder than existential one.
In the light of our decision we applied various new techniques and less constructive approaches. We connected these with previously acquired knowledge and we hope for some results during the next week.

Week 6

We scoped various new ideas applying our accumulated knowledge. We found dualities of behavior and structural properties between small and big sources as well as acquired wide intuitive view of underlying structural processes.
We adopted different approximation approach as well as formulated new existential properties of minimum counter-examples. The latter has been formulated even in a form of mathematical game. We hope to exploit this formulation and prove stronger approximation results and reduce minimum counter-example space in future research.

Week 7

In the 7th week, we found further properties and bounds of minimum counter-examples.
We also spent significant portion of our time working on simplicial complex embedding problem.

---

References

[1] A. Bonato, J. Janssen, E. Roshanbin, Burning a graph is hard, Preprint 2015
[2] A. Bonato, J. Janssen, E. Roshanbin, How to burn a graph, arXiv:1507.06524
[3] S. Bessy and D. Rautenbach, Bounds, Approximation, and Hardness for the Burning Number, arXiv:1511.06023

Presentations

Our intro project presentation

---