A Central Limit Theorem for Almost Local Additive Tree Functionals

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00510355" target="_blank" >RIV/67985807:_____/20:00510355 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00453-019-00622-4" target="_blank" >http://dx.doi.org/10.1007/s00453-019-00622-4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-019-00622-4" target="_blank" >10.1007/s00453-019-00622-4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Central Limit Theorem for Almost Local Additive Tree Functionals

Popis výsledku v původním jazyce

An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Svante Janson recently proved a central limit theorem for additive functionals of conditioned Galton–Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are “almost local” in a certain sense, thus covering a wider range of functionals. The notion of almost local functional intuitively means that the toll function can be approximated well by considering only a neighbourhood of the root. Our main result is illustrated by several explicit examples including natural graph-theoretic parameters such as the number of independent sets, the number of matchings, and the number of dominating sets. We also cover a functional stemming from a tree reduction procedure that was studied by Hackl, Heuberger, Kropf, and Prodinger.

Název v anglickém jazyce

A Central Limit Theorem for Almost Local Additive Tree Functionals

Popis výsledku anglicky

An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Svante Janson recently proved a central limit theorem for additive functionals of conditioned Galton–Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are “almost local” in a certain sense, thus covering a wider range of functionals. The notion of almost local functional intuitively means that the toll function can be approximated well by considering only a neighbourhood of the root. Our main result is illustrated by several explicit examples including natural graph-theoretic parameters such as the number of independent sets, the number of matchings, and the number of dominating sets. We also cover a functional stemming from a tree reduction procedure that was studied by Hackl, Heuberger, Kropf, and Prodinger.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GJ16-07822Y" target="_blank" >GJ16-07822Y: Extremální teorie grafů a aplikace</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithmica

ISSN

0178-4617

e-ISSN

—

Svazek periodika

82

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

642-679

Kód UT WoS článku

000511594700007

EID výsledku v databázi Scopus

2-s2.0-85073825080