License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.2
URN: urn:nbn:de:0030-drops-160886
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16088/
Go to the corresponding LIPIcs Volume Portal

Bellin, Etienne

On the Independence Number of Random Trees via Tricolourations

pdf-format:
LIPIcs-AofA-2022-2.pdf (0.7 MB)

Abstract

We are interested in the independence number of large random simply generated trees and related parameters, such as their matching number or the kernel dimension of their adjacency matrix. We express these quantities using a canonical tricolouration, which is a way to colour the vertices of a tree with three colours. As an application we obtain limit theorems in L^p for the renormalised independence number in large simply generated trees (including large size-conditioned Bienaymé-Galton-Watson trees).

BibTeX - Entry

@InProceedings{bellin:LIPIcs.AofA.2022.2,
  author =	{Bellin, Etienne},
  title =	{{On the Independence Number of Random Trees via Tricolourations}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16088},
  URN =		{urn:nbn:de:0030-drops-160886},
  doi =		{10.4230/LIPIcs.AofA.2022.2},
  annote =	{Keywords: Independence number, simply generated tree, Galton-Watson tree, tricolouration}
}

Keywords: Independence number, simply generated tree, Galton-Watson tree, tricolouration
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI