Tata Institute of Fundamental Research
On The Linear Arboricity Conjecture
STCS Student Seminar
Speaker:
Sreejata Kishor Bhattacharya
Date:
Friday, 11 Nov 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
A linear forest is a forest in which every connected component is a line. The linear arboricity of an undirected graph is the minimum t such that the edge set can be partitioned into t subsets, each of which forms a linear forest.
Harari introduced this quantity as one of the covering invariants of graphs. Harari, Exoo and Akiyama (1981) made the following conjecture: the linear arboricity of any d regular graph is ceil(d+1)/2 (the lower bound is easy to prove; the non-trivial part is the upper bound).
Alon proved in 1988 that the linear arboricity of a d regular graph is at most d/2 + O(d^{3/4+\epsilon}) for any $\epsilon > 0$. The proof uses Lovasz Local Lemma and probabilistic method in very unexpected situations. We shall present this proof.
Link to paper: https://link.springer.com/article/10.1007/BF02783300
| Speaker: | Sreejata Kishor Bhattacharya |
| Date: | Friday, 11 Nov 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
A linear forest is a forest in which every connected component is a line. The linear arboricity of an undirected graph is the minimum t such that the edge set can be partitioned into t subsets, each of which forms a linear forest.
Harari introduced this quantity as one of the covering invariants of graphs. Harari, Exoo and Akiyama (1981) made the following conjecture: the linear arboricity of any d regular graph is ceil(d+1)/2 (the lower bound is easy to prove; the non-trivial part is the upper bound).
Alon proved in 1988 that the linear arboricity of a d regular graph is at most d/2 + O(d^{3/4+\epsilon}) for any $\epsilon > 0$. The proof uses Lovasz Local Lemma and probabilistic method in very unexpected situations. We shall present this proof.
Link to paper: https://link.springer.com/article/10.1007/BF02783300
Harari introduced this quantity as one of the covering invariants of graphs. Harari, Exoo and Akiyama (1981) made the following conjecture: the linear arboricity of any d regular graph is ceil(d+1)/2 (the lower bound is easy to prove; the non-trivial part is the upper bound).
Alon proved in 1988 that the linear arboricity of a d regular graph is at most d/2 + O(d^{3/4+\epsilon}) for any $\epsilon > 0$. The proof uses Lovasz Local Lemma and probabilistic method in very unexpected situations. We shall present this proof.
Link to paper: https://link.springer.com/article/10.1007/BF02783300