Search Results

Documents authored by Féray, Valentin

Document
DOI: 10.4230/LIPIcs.AofA.2026.18
Large Deviation Principles for Pattern-Avoiding Permutations, and Limit Shapes for Constrained Mallows Permutations

Authors: Thomas Budzinski, Victor Dubach, Valentin Féray, Mohamed Slim Kammoun, and Mylene Maïda

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We study Mallows random permutations conditioned to avoid a given pattern α of length 3, for which we find limit shapes in the space of permutons when the bias parameter is of the form e^(β/n). Along the way, we provide parametrizations for α-avoiding permutons, and establish large deviation principles for uniform α-avoiding permutations.
Cite as

Thomas Budzinski, Victor Dubach, Valentin Féray, Mohamed Slim Kammoun, and Mylene Maïda. Large Deviation Principles for Pattern-Avoiding Permutations, and Limit Shapes for Constrained Mallows Permutations. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{budzinski_et_al:LIPIcs.AofA.2026.18,
  author =	{Budzinski, Thomas and Dubach, Victor and F\'{e}ray, Valentin and Kammoun, Mohamed Slim and Ma\"{i}da, Mylene},
  title =	{{Large Deviation Principles for Pattern-Avoiding Permutations, and Limit Shapes for Constrained Mallows Permutations}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.18},
  URN =		{urn:nbn:de:0030-drops-262895},
  doi =		{10.4230/LIPIcs.AofA.2026.18},
  annote =	{Keywords: Permutations, Pattern avoidance, Large deviations, Mallows distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.21
Binary Search Trees of Permuton Samples

Authors: Benoît Corsini, Victor Dubach, and Valentin Féray

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Binary search trees (BST) are a popular type of structure when dealing with ordered data. They allow efficient access and modification of data, with their height corresponding to the worst retrieval time. From a probabilistic point of view, BSTs associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform permutation. We consider here the case where the input comes from i.i.d. random points in the plane with law μ, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree only depends on the behavior of the measure μ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures μ. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates.
Cite as

Benoît Corsini, Victor Dubach, and Valentin Féray. Binary Search Trees of Permuton Samples. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{corsini_et_al:LIPIcs.AofA.2024.21,
  author =	{Corsini, Beno\^{i}t and Dubach, Victor and F\'{e}ray, Valentin},
  title =	{{Binary Search Trees of Permuton Samples}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.21},
  URN =		{urn:nbn:de:0030-drops-204562},
  doi =		{10.4230/LIPIcs.AofA.2024.21},
  annote =	{Keywords: Binary search trees, random permutations, permutons}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.23
A Canonical Tree Decomposition for Chirotopes

Authors: Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the concept of mutually avoiding sets, and adapts in some sense the modular decomposition of graphs in the world of chirotopes. The associated tree always exists and is unique up to some appropriate constraints. We also show how to compute the number of triangulations of a chirotope efficiently, starting from its tree and the (weighted) numbers of triangulations of its parts.
Cite as

Mathilde Bouvel, Valentin Feray, Xavier Goaoc, and Florent Koechlin. A Canonical Tree Decomposition for Chirotopes. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bouvel_et_al:LIPIcs.SoCG.2024.23,
  author =	{Bouvel, Mathilde and Feray, Valentin and Goaoc, Xavier and Koechlin, Florent},
  title =	{{A Canonical Tree Decomposition for Chirotopes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.23},
  URN =		{urn:nbn:de:0030-drops-199680},
  doi =		{10.4230/LIPIcs.SoCG.2024.23},
  annote =	{Keywords: Order type, modular decomposition, counting triangulations, mutually avoiding point sets, generating functions, rewriting systems}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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