Logotyp: till Uppsala universitets webbplats

uu.sePublikationer från Uppsala universitet
EnglishSvenskaNorsk
Ändra sökning
ExporteraLänk till posten
Permanent länk

Direktlänk
BETA

Projekt

Projekttyp/Bidragsform
Projektbidrag
Titel [sv]
Analytiska och probabilistiska verktyg för studiet av slumpträd
Titel [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.
Publikationer (1 of 1) Visa alla publikationer
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
Öppna denna publikation i ny flik eller fönster >>Trees maximizing the number of almost-perfect matchings
Visa övriga...
2025 (Engelska)Ingår i: Applicable Analysis and Discrete Mathematics, ISSN 1452-8630, Vol. 19, nr 1, s. 104-129Artikel i tidskrift (Refereegranskat) 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.
Ort, förlag, år, upplaga, sidor
National Library of Serbia, 2025
Nyckelord
Trees, Matching, Almost-perfect matching, Maximal matching, Weighted Hosoya index
Nationell ämneskategori
Diskret matematik
Identifikatorer
urn:nbn:se:uu:diva-556061 (URN)10.2298/AADM230824006C (DOI)001476838200007 ()
Forskningsfinansiär
Knut och Alice Wallenbergs Stiftelse, KAW 2017.0112Vetenskapsrådet, 2022-04030
Tillgänglig från: 2025-05-09 Skapad: 2025-05-09 Senast uppdaterad: 2025-05-09Bibliografiskt granskad
ProjektledareWagner, Stephan
Koordinerande organisation
Uppsala universitet
Forskningsfinansiär
Tidsperiod
2023-01-01 － 2026-12-31
Nationell ämneskategori
Diskret matematikSannolikhetsteori och statistik
Identifikatorer
DiVA, id: project:8895Projekt id: 2022-04030_VR

Sök vidare i DiVA

Diskret matematikSannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar
v. 2.47.0
|
WCAG
|
Uppsala universitetsbibliotek
|
Fråga biblioteket
|
Logga in i DiVA
|
Söka och länka i DiVA