Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

THE CYCLES IN GEOMETRIC RANDOM GRAPHS ON DISCRETE CIRCLE

Yao, Xinxu LU (2026) In Master's Theses in Mathematical Sciences MASM02 20261
Mathematical Statistics
Abstract
This thesis studies a geometric random graph model on the discrete circle Z/N Z, in which an
edge between distinct vertices u and v is present independently with probability
p(u, v) = min{cN^{-(1-α)}ρ(u, v)^{-α},1}, 0 < α < 1,
where ρ(u, v) is the graph distance. The main focus is on the number of cycles of a fixed
length, which provides a natural measure of the deviation from a tree-like structure. The
expected number of k-cycles is shown to exhibit different asymptotic regimes depending on
the relationship between k and the decay parameter α. More precisely, it converges to a finite constant when k(1 − α) > 1, grows logarithmically in the critical case k(1 − α) = 1, and grows polynomially when k(1 − α) < 1. In addition, when α <... (More)
This thesis studies a geometric random graph model on the discrete circle Z/N Z, in which an
edge between distinct vertices u and v is present independently with probability
p(u, v) = min{cN^{-(1-α)}ρ(u, v)^{-α},1}, 0 < α < 1,
where ρ(u, v) is the graph distance. The main focus is on the number of cycles of a fixed
length, which provides a natural measure of the deviation from a tree-like structure. The
expected number of k-cycles is shown to exhibit different asymptotic regimes depending on
the relationship between k and the decay parameter α. More precisely, it converges to a finite constant when k(1 − α) > 1, grows logarithmically in the critical case k(1 − α) = 1, and grows polynomially when k(1 − α) < 1. In addition, when α < 2/3, the number of k-cycles is asymptotically Poisson distributed. (Less)
Popular Abstract (Swedish)
I detta examensarbete studeras en geometrisk slumpgraf på en diskret cirkel, där två punkter kopplas samman slumpmässigt med en sannolikhet som avtar med avståndet mellan dem. Modellen är intressant eftersom samspelet mellan slump och geometri kan ge upphov till strukturer som skiljer sig från dem i mer klassiska slumpgrafer. Arbetet fokuserar på cykler av given längd, det vill säga slutna slingor i grafen. Sådana cykler ger information om grafens lokala struktur och om hur långt den avviker från en trädliknande uppbyggnad. Resultaten visar att det förväntade antalet cykler kan uppvisa olika typer av asymptotiskt beteende beroende på modellens parametrar: i vissa fall förblir det begränsat, i andra växer det logaritmiskt, och i ytterligare... (More)
I detta examensarbete studeras en geometrisk slumpgraf på en diskret cirkel, där två punkter kopplas samman slumpmässigt med en sannolikhet som avtar med avståndet mellan dem. Modellen är intressant eftersom samspelet mellan slump och geometri kan ge upphov till strukturer som skiljer sig från dem i mer klassiska slumpgrafer. Arbetet fokuserar på cykler av given längd, det vill säga slutna slingor i grafen. Sådana cykler ger information om grafens lokala struktur och om hur långt den avviker från en trädliknande uppbyggnad. Resultaten visar att det förväntade antalet cykler kan uppvisa olika typer av asymptotiskt beteende beroende på modellens parametrar: i vissa fall förblir det begränsat, i andra växer det logaritmiskt, och i ytterligare andra växer det polynomiellt. I ett visst parameterområde visas dessutom att antalet cykler asymptotiskt följer en Poissonfördelning. (Less)
Please use this url to cite or link to this publication:
author
Yao, Xinxu LU
supervisor
organization
course
MASM02 20261
year
type
H2 - Master's Degree (Two Years)
subject
keywords
Geometric random graph, Subgraphs, Phase transition
publication/series
Master's Theses in Mathematical Sciences
report number
LUNFMS-3138-2026
ISSN
1404-6342
other publication id
2026:E20
language
English
id
9226480
date added to LUP
2026-05-25 16:45:10
date last changed
2026-06-04 15:38:59
@misc{9226480,
  abstract     = {{This thesis studies a geometric random graph model on the discrete circle Z/N Z, in which an
edge between distinct vertices u and v is present independently with probability
p(u, v) = min{cN^{-(1-α)}ρ(u, v)^{-α},1}, 0 < α < 1,
where ρ(u, v) is the graph distance. The main focus is on the number of cycles of a fixed
length, which provides a natural measure of the deviation from a tree-like structure. The
expected number of k-cycles is shown to exhibit different asymptotic regimes depending on
the relationship between k and the decay parameter α. More precisely, it converges to a finite constant when k(1 − α) > 1, grows logarithmically in the critical case k(1 − α) = 1, and grows polynomially when k(1 − α) < 1. In addition, when α < 2/3, the number of k-cycles is asymptotically Poisson distributed.}},
  author       = {{Yao, Xinxu}},
  issn         = {{1404-6342}},
  language     = {{eng}},
  note         = {{Student Paper}},
  series       = {{Master's Theses in Mathematical Sciences}},
  title        = {{THE CYCLES IN GEOMETRIC RANDOM GRAPHS ON DISCRETE CIRCLE}},
  year         = {{2026}},
}