Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts

ABSTRACT We consider maximum rooted tree extension counts in random graphs, that is, we consider where counts the number of copies of a given tree in rooted at vertex . We determine the asymptotics of when the random graph is not too sparse, specifically when the edge probability satisfies . The problem is more difficult in the sparser regime , where we determine the asymptotics of for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of changes as we vary , due to different mechanisms that can make the maximum large.

Authors

Institutions

Publication Details

Journal
Random Structures and Algorithms
Published
2026-11-16
DOI
https://doi.org/10.1002/rsa.70096
Citations
2
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts

Lutz Warnke, Matas Šileikis
2 citations
Random Structures and Algorithms
Limits and Structures in Graph Theory
article

Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts

Lutz Warnke, Matas Šileikis
article en
2 citations

Abstract

ABSTRACT We consider maximum rooted tree extension counts in random graphs, that is, we consider where counts the number of copies of a given tree in rooted at vertex . We determine the asymptotics of when the random graph is not too sparse, specifically when the edge probability satisfies . The problem is more difficult in the sparser regime , where we determine the asymptotics of for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of changes as we vary , due to different mechanisms that can make the maximum large.

Random Structures and AlgorithmsVol. 69(4)
Vilnius University (LT), Czech Academy of Sciences (CZ), Universidade Federal de Pernambuco (BR), Pontifícia Universidade Católica do Rio de Janeiro (BR), University of California San Diego (US), Vilnius University of Applied Sciences (LT), Czech Academy of Sciences, Institute of Computer Science (CZ)
National Science Foundation, Grantová Agentura České Republiky, Conselho Nacional de Desenvolvimento Científico e Tecnológico, Akademie Věd České Republiky, Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon