Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
EnglishSvenskaNorsk
Change search
ExportLink to record
Permanent link

Direct link
BETA

Project

Project type/Form of grant
Project grant
Title [sv]
Analytiska och probabilistiska verktyg för studiet av slumpträd
Title [en]
Analytic and probabilistic tools for the study of random trees
Abstract [sv]
Träd är enkla objekt som består av noder och kanter som förbinder dem, men de spelar trots detta en viktig roll inom många områden både inom och utanför matematiken: de är grundläggande datastrukturer och används i många viktiga algoritmer, till exempel för sortering och sökning; de förekommer också i biologi som fylogenetiska träd, där de modellerar evolution.Syftet med detta projekt är att utveckla metoder för att analysera slumpträd och andra slumpmässiga strukturer, och att förbättra vår förståelse för olika modeller av slumpträd. Det finns många olika sätt att generera slumpmässiga träd: exempelvis genom att slumpmässigt välja ett träd från en mängd av alla möjligheter, eller genom att låta dem växa enligt en slumpmässig process, där noder och kanter läggs till steg för steg. I detta projekt kommer vi att både studera klassiska välstuderade modeller samt modeller som ännu inte har studerats noggrant men har intressanta egenskaper.I synnerhet kommer vi att bevisa gränsvärdesatser för så kallade additiva parametrar och andra allmänna typer av parametrar. Genererande funktioner är ett viktigt verktyg i detta samband eftersom de möjliggör att uttrycka strukturella egenskaper som ekvationer. Ibland behöver man oändliga ekvationssystem för att beskriva egenskaper hos slumpträd och andra diskreta strukturer, och en allmän teori om sådana ekvationssystem saknas. Ett viktigt mål är därför att utveckla metoder för att studera oändliga ekvationssystem.Denna forskning motiveras delvis av tillämpningar inom datavetenskap och biologi. Kunskap om fördelningen av trädparametrar ger insikter i olika algoritmers prestanda. Trädparametrar spelar också en viktig roll i fylogenetisk forskning där egenskaper hos slumpmässigt genererade fylogenetiska träd betraktas.Projektet kombinerar olika matematiska ämnen: särskilt enumerativ kombinatorik och sannolikhetsteori, men också till exempel klassisk reell och komplex analys.
Abstract [en]
The main goal of this project is to develop new tools for the study of random trees and related discrete structures. In particular, we aim to develop general limit theorems that cover different models of randomness as well as different structural aspects. Research on random trees is partly motivated by questions arising in other areas, such as phylogenetics and computer science.One specific goal is to develop general theorems to deal with infinite systems of functional equations for generating functions. While the finite case is quite well understood, infinite systems are harder to deal with, and a systematic treatment is lacking. Such systems occur in the study of random trees, but also in other contexts. A second goal is to develop new limit theorems for additive tree functionals and other general classes of tree functionals.Lastly, we investigate new models of random trees that we expect to exhibit unusual and interesting behaviour. The most classical types of random tree models that have been studied extensively are trees of logarithmic height and trees of square root height. Probabilistic models that can interpolate between these two worlds will allow us to observe new phenomena.The project links different parts of mathematics, especially enumerative combinatorics and probability theory, but real and complex analysis also play a significant role. Generating functions and analytic combinatorics are blended with probabilistic ingredients.
Publications (1 of 1) Show all publications
Cambie, S., McCoy, B., Sharma, G., Wagner, S. & Yap, C. (2025). Trees maximizing the number of almost-perfect matchings. Applicable Analysis and Discrete Mathematics, 19(1), 104-129
Open this publication in new window or tab >>Trees maximizing the number of almost-perfect matchings
Show others...
2025 (English)In: Applicable Analysis and Discrete Mathematics, ISSN 1452-8630, Vol. 19, no 1, p. 104-129Article in journal (Refereed) Published
Abstract [en]

We characterize the extremal trees that maximize the number of almost-perfect matchings, which are matchings covering all but one or two vertices, and those that maximize the number of strong almost-perfect matchings, which are matchings missing only one or two leaves. We also determine the trees that minimize the number of maximal matchings. We apply these results to extremal problems on the weighted Hosoya index for several choices of vertex-degree-based weight function.
Place, publisher, year, edition, pages
National Library of Serbia, 2025
Keywords
Trees, Matching, Almost-perfect matching, Maximal matching, Weighted Hosoya index
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:uu:diva-556061 (URN)10.2298/AADM230824006C (DOI)001476838200007 ()
Funder
Knut and Alice Wallenberg Foundation, KAW 2017.0112Swedish Research Council, 2022-04030
Available from: 2025-05-09 Created: 2025-05-09 Last updated: 2025-05-09Bibliographically approved
Principal InvestigatorWagner, Stephan
Coordinating organisation
Uppsala University
Funder
Period
2023-01-01 － 2026-12-31
National Category
Discrete MathematicsProbability Theory and Statistics
Identifiers
DiVA, id: project:8895Project, id: 2022-04030_VR

Search in DiVA

Discrete MathematicsProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
v. 2.47.0
|
WCAG
|
Uppsala University Library
|
Ask the Library
|
Log in to DiVA
|
Search and link in DiVA