Search Results

Documents authored by Johansson, Tony

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.45
The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree

Authors: Tony Johansson

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We consider a random walk process, introduced by Orenshtein and Shinkar [Tal Orenshtein and Igor Shinkar, 2014], which prefers to visit previously unvisited edges, on the random r-regular graph G_r for any odd r >= 3. We show that this random walk process has asymptotic vertex and edge cover times 1/(r-2)n log n and r/(2(r-2))n log n, respectively, generalizing the result from [Cooper et al., to appear] from r = 3 to any larger odd r. This completes the study of the vertex cover time for fixed r >= 3, with [Petra Berenbrink et al., 2015] having previously shown that G_r has vertex cover time asymptotic to rn/2 when r >= 4 is even.
Cite as

Tony Johansson. The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{johansson:LIPIcs.APPROX-RANDOM.2018.45,
  author =	{Johansson, Tony},
  title =	{{The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.45},
  URN =		{urn:nbn:de:0030-drops-94494},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.45},
  annote =	{Keywords: Random walk, random regular graph, cover time}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.9
Permutations in Binary Trees and Split Trees

Authors: Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We investigate the number of permutations that occur in random node labellings of trees. This is a generalisation of the number of subpermutations occuring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees [Cai et al., 2017]. We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye [Devroye, 1998]. Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree with high probability the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.
Cite as

Michael Albert, Cecilia Holmgren, Tony Johansson, and Fiona Skerman. Permutations in Binary Trees and Split Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.AofA.2018.9,
  author =	{Albert, Michael and Holmgren, Cecilia and Johansson, Tony and Skerman, Fiona},
  title =	{{Permutations in Binary Trees and Split Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.9},
  URN =		{urn:nbn:de:0030-drops-89025},
  doi =		{10.4230/LIPIcs.AofA.2018.9},
  annote =	{Keywords: random trees, split trees, permutations, inversions, cumulant}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.15
Inversions in Split Trees and Conditional Galton-Watson Trees

Authors: Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].
Cite as

Xing Shi Cai, Cecilia Holmgren, Svante Janson, Tony Johansson, and Fiona Skerman. Inversions in Split Trees and Conditional Galton-Watson Trees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.AofA.2018.15,
  author =	{Cai, Xing Shi and Holmgren, Cecilia and Janson, Svante and Johansson, Tony and Skerman, Fiona},
  title =	{{Inversions in Split Trees and Conditional Galton-Watson Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.15},
  URN =		{urn:nbn:de:0030-drops-89085},
  doi =		{10.4230/LIPIcs.AofA.2018.15},
  annote =	{Keywords: inversions, random trees, split trees, Galton-Watson trees, permutation, cumulant}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.16
The Cover Time of a Biased Random Walk on a Random Cubic Graph

Authors: Colin Cooper, Alan Frieze, and Tony Johansson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.
Cite as

Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.AofA.2018.16,
  author =	{Cooper, Colin and Frieze, Alan and Johansson, Tony},
  title =	{{The Cover Time of a Biased Random Walk on a Random Cubic Graph}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.16},
  URN =		{urn:nbn:de:0030-drops-89097},
  doi =		{10.4230/LIPIcs.AofA.2018.16},
  annote =	{Keywords: Random walk, random regular graph, cover time}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact