Search Results

Documents authored by Louf, Baptiste

Document
DOI: 10.4230/LIPIcs.ITCS.2024.78
Modularity and Graph Expansion

Authors: Baptiste Louf, Colin McDiarmid, and Fiona Skerman

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We relate two important notions in graph theory: expanders which are highly connected graphs, and modularity a parameter of a graph that is primarily used in community detection. More precisely, we show that a graph having modularity bounded below 1 is equivalent to it having a large subgraph which is an expander. We further show that a connected component H will be split in an optimal partition of the host graph G if and only if the relative size of H in G is greater than an expansion constant of H. This is a further exploration of the resolution limit known for modularity, and indeed recovers the bound that a connected component H in the host graph G will not be split if e(H) < √{2e(G)}.
Cite as

Baptiste Louf, Colin McDiarmid, and Fiona Skerman. Modularity and Graph Expansion. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 78:1-78:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louf_et_al:LIPIcs.ITCS.2024.78,
  author =	{Louf, Baptiste and McDiarmid, Colin and Skerman, Fiona},
  title =	{{Modularity and Graph Expansion}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{78:1--78:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.78},
  URN =		{urn:nbn:de:0030-drops-196063},
  doi =		{10.4230/LIPIcs.ITCS.2024.78},
  annote =	{Keywords: edge expansion, modularity, community detection, resolution limit, conductance}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.6
Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps

Authors: Guillaume Chapuy, Baptiste Louf, and Harriet Walsh

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.
Cite as

Guillaume Chapuy, Baptiste Louf, and Harriet Walsh. Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chapuy_et_al:LIPIcs.AofA.2022.6,
  author =	{Chapuy, Guillaume and Louf, Baptiste and Walsh, Harriet},
  title =	{{Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{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.2022.6},
  URN =		{urn:nbn:de:0030-drops-160921},
  doi =		{10.4230/LIPIcs.AofA.2022.6},
  annote =	{Keywords: Random partitions, limit shapes, transposition factorisations, map enumeration, Hurwitz numbers, RSK algorithm, giant components}
}
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 About DROPS Imprint Privacy Contact