Logo: to the web site of Uppsala University

uu.sePublikasjoner fra Uppsala universitet
EnglishSvenskaNorsk
Endre søk
ExporteraLink to record
Permanent link

Direct link
BETA

Prosjekt

Prosjekttyp/Bidragsform
Project grant
Tittel [sv]
Analytiska och probabilistiska verktyg för studiet av slumpträd
Tittel [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.
Publikasjoner (1 av 1) Visa alla publikasjoner
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
Åpne denne publikasjonen i ny fane eller vindu >>Trees maximizing the number of almost-perfect matchings
Vise andre…
2025 (engelsk)Inngår i: Applicable Analysis and Discrete Mathematics, ISSN 1452-8630, Vol. 19, nr 1, s. 104-129Artikkel i tidsskrift (Fagfellevurdert) 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.
sted, utgiver, år, opplag, sider
National Library of Serbia, 2025
Emneord
Trees, Matching, Almost-perfect matching, Maximal matching, Weighted Hosoya index
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-556061 (URN)10.2298/AADM230824006C (DOI)001476838200007 ()
Forskningsfinansiär
Knut and Alice Wallenberg Foundation, KAW 2017.0112Swedish Research Council, 2022-04030
Tilgjengelig fra: 2025-05-09 Laget: 2025-05-09 Sist oppdatert: 2025-05-09bibliografisk kontrollert
Principal InvestigatorWagner, Stephan
Koordinerande organisasjon
Uppsala universitet
Forskningsfinansiär
Tidsperiod
2023-01-01 － 2026-12-31
HSV kategori
Discrete MathematicsProbability Theory and Statistics
Identifikatorer
DiVA, id: project:8895Prosjekt id: 2022-04030_VR
v. 2.47.0
|
WCAG
|
Uppsala universitetsbibliotek
|
Spør biblioteket
|
DiVA Logg in
|
Søk og lenke i DiVA (svensk)