22 results on '"Féray, Valentin"'
Search Results
2. Binary search trees of permuton samples
- Author
-
Corsini, Benoît, Dubach, Victor, and Féray, Valentin
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05C05, 05A05 - Abstract
Binary search trees (BST) are a popular type of data structure when dealing with ordered data. Indeed, they enable one to access and modify data efficiently, with their height corresponding to the worst retrieval time. From a probabilistic point of view, binary search trees associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform random permutation. We consider here the case where the input comes from i.i.d. random points in the plane with law $\mu$, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree depends on the behavior of the measure $\mu$ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures $\mu$. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates., Comment: 27 pages, 6 figures
- Published
- 2024
3. Dense and nondense limits for uniform random intersection graphs
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, and Pierrot, Adeline
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,05C62, 05C80 - Abstract
We obtain the scaling limits of random graphs drawn uniformly in three families of intersection graphs: permutation graphs, circle graphs, and unit interval graphs. The two first families typically generate dense graphs, in these cases we prove a.s. convergence to an explicit deterministic graphon. Uniform unit interval graphs are nondense and we prove convergence in the sense of Gromov-Prokhorov after normalization of the distances: the limiting object is the interval $[0,1]$ endowed with a random metric defined through a Brownian excursion. Asymptotic results for the number of cliques of size $k$ ($k$ fixed) in a uniform random graph in each of these three families are also given. In all three cases, an important ingredient of the proof is that, for indecomposable graphs in each class (where the notion of indecomposability depends on the class), the combinatorial object defining the graph (permutation, matching, or intervals) is essentially unique.
- Published
- 2024
4. Asymptotic normality of pattern counts in conjugacy classes
- Author
-
Féray, Valentin and Kammoun, Mohamed Slim
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
We prove, under mild conditions on fixed points and two cycles, the asymptotic normality of vincular pattern counts for a permutation chosen uniformly at random in a conjugacy class.Additionally, we prove that the limiting variance is always non-degenerate for classical pattern counts. The proof uses weighted dependency graphs.
- Published
- 2023
5. A determinantal point process approach to scaling and local limits of random Young tableaux
- Author
-
Borga, Jacopo, Boutillier, Cédric, Féray, Valentin, and Méliot, Pierre-Loïc
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,Mathematics - Representation Theory - Abstract
We obtain scaling and local limit results for large random Young tableaux of fixed shape $\lambda^0$ via the asymptotic analysis of a determinantal point process due to Gorin and Rahman (2019). More precisely, we prove: (1) an explicit description of the limiting surface of a uniform random Young tableau of shape $\lambda^0$, based on solving a complex-valued polynomial equation; (2) a simple criteria to determine if the limiting surface is continuous in the whole domain; (3) and a local limit result in the bulk of a random Poissonized Young tableau of shape $\lambda^0$. Our results have several consequences, for instance: they lead to explicit formulas for the limiting surface of $L$-shaped tableaux, generalizing the results of Pittel and Romik (2007) for rectangular shapes; they imply that the limiting surface for $L$-shaped tableaux is discontinuous for almost-every $L$-shape; and they give a new one-parameter family of infinite random Young tableaux, constructed from the so-called random infinite bead process., Comment: New version including referee's corrections, accepted for publication in Annals of Probability
- Published
- 2023
6. The permuton limit of random recursive separable permutations
- Author
-
Féray, Valentin and Rivera-Lopez, Kelvin
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05A05 - Abstract
We introduce and study a simple Markovian model of random separable permutations. Our first main result is the almost sure convergence of these permutations towards a random limiting object in the sense of permutons, which we call the recursive separable permuton. We then prove several results on this new limiting object: a characterization of its distribution via a fixed-point equation, a combinatorial formula for its expected pattern densities, an explicit integral formula for its intensity measure, and lastly, we prove that its distribution is absolutely singular with respect to that of the Brownian separable permuton, which is the large size limit of uniform random separable permutations., Comment: 37 pages, 15 figures. v2 incorporates referee's suggestions
- Published
- 2023
7. Wiener Indices of Minuscule Lattices
- Author
-
Defant, Colin, Féray, Valentin, Nadeau, Philippe, and Williams, Nathan
- Subjects
Mathematics - Combinatorics - Abstract
The Wiener index of a finite graph G is the sum over all pairs (p, q) of vertices of G of the distance between p and q. When P is a finite poset, we define its Wiener index as the Wiener index of the graph of its Hasse diagram. In this paper, we find exact expressions for the Wiener indices of the distributive lattices of order ideals in minuscule posets. For infinite families of such posets, we also provide results on the asymptotic distribution of the distance between two random order ideals., Comment: 16 pages, 5 figures
- Published
- 2023
8. A logical limit law for $231$-avoiding permutations
- Author
-
Albert, Michael, Bouvel, Mathilde, Féray, Valentin, and Noy, Marc
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability ,05A16, 60C05 (primary), 03C13 (secondary) - Abstract
We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behavior and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis., Comment: 15 pages; version 3 is the final version, ready for publication in DMTCS
- Published
- 2022
- Full Text
- View/download PDF
9. Scaling limit of graph classes through split decomposition
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, and Pierrot, Adeline
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05C80, 05A16 - Abstract
We prove that Aldous' Brownian CRT is the scaling limit, with respect to the Gromov--Prokhorov topology, of uniform random graphs in each of the three following families of graphs: distance-hereditary graphs, $2$-connected distance-hereditary graphs and $3$-leaf power graphs. Our approach is based on the split decomposition and on analytic combinatorics., Comment: 47 pages
- Published
- 2022
10. Components in meandric systems and the infinite noodle
- Author
-
Féray, Valentin and Thévenin, Paul
- Subjects
Mathematics - Probability ,60C05 - Abstract
We investigate here the asymptotic behaviour of a large typical meandric system. More precisely, we show the quenched local convergence of a random uniform meandric system $M_n$ on $2n$ points, as $n \rightarrow \infty$, towards the infinite noodle introduced by Curien, Kozma, Sidoravicius and Tournier ({\em Ann. Inst. Henri Poincar\'e D}, {6}(2):221--238, 2019). As a consequence, denoting by $cc( M_n)$ the number of connected components of $ M_n$, we prove the convergence in probability of $cc(M_n)/n$ to some constant $\kappa$, answering a question raised independently by Goulden--Nica--Puder ({\em Int. Math. Res. Not.}, 2020(4):983--1034, 2020) and Kargin ({\em Journal of Statistical Physics}, 181(6):2322--2345, 2020). This result also provides information on the asymptotic geometry of the Hasse diagram of the lattice of non-crossing partitions. Finally, we obtain expressions of the constant $\kappa$ as infinite sums over meanders, which allows us to compute upper and lower approximations of $\kappa$., Comment: 22 pages, 7 figures. v2: addition of an erratum
- Published
- 2022
11. Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Drmota, Michael, Féray, Valentin, Gerin, Lucas, Maazoun, Mickaël, and Pierrot, Adeline
- Subjects
Combinatorial graph theory ,combinatorial probability ,cographs ,random graphs ,graphons ,self-similarity - Abstract
This paper is interested in independent sets (or equivalently, cliques) in uniform random cographs. We also study their permutation analogs, namely, increasing subsequences in uniform random separable permutations. First, we prove that, with high probability as \(n\) gets large, the largest independent set in a uniform random cograph with \(n\) vertices has size \(o(n)\). This answers a question of Kang, McDiarmid, Reed and Scott. Using the connection between graphs and permutations via inversion graphs, we also give a similar result for the longest increasing subsequence in separable permutations. These results are proved using the self-similarity of the Brownian limits of random cographs and random separable permutations, and actually apply more generally to all families of graphs and permutations with the same limit. Second, and unexpectedly given the above results, we show that for \(\beta >0\) sufficiently small, the expected number of independent sets of size \(\beta n\) in a uniform random cograph with \(n\) vertices grows exponentially fast with \(n\). We also prove a permutation analog of this result. This time the proofs rely on singularity analysis of the associated bivariate generating functions.Mathematics Subject Classifications: 60C05, 05C80, 05C69, 05A05Keywords: Combinatorial graph theory, combinatorial probability, cographs, random graphs, graphons, self-similarity
- Published
- 2022
12. Random generation and scaling limits of fixed genus factorizations into transpositions
- Author
-
Féray, Valentin, Louf, Baptiste, and Thévenin, Paul
- Published
- 2022
- Full Text
- View/download PDF
13. Scaling limits of permutation classes with a finite specification: A dichotomy
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, Maazoun, Mickaël, and Pierrot, Adeline
- Published
- 2022
- Full Text
- View/download PDF
14. A logical limit law for $231$-avoiding permutations
- Author
-
Albert, Michael, primary, Bouvel, Mathilde, additional, Féray, Valentin, additional, and Noy, Marc, additional
- Published
- 2024
- Full Text
- View/download PDF
15. Erratum to Components in Meandric Systems and the Infinite Noodle.
- Author
-
Féray, Valentin and Thévenin, Paul
- Subjects
- *
NOODLES , *CONTINUOUS functions - Abstract
This document is an erratum to a paper titled "Components in Meandric Systems and the Infinite Noodle." The erratum acknowledges a missing argument in the proof of Proposition 5 in the original paper. It also refers to Proposition 1 and Proposition 2 from the original paper, which discuss the convergence of random meandric systems and well-parenthesized words, respectively. The document provides equations and a lemma related to these propositions. The erratum concludes by stating that the difference between two equations is the use of the same root in both well-parenthesized words. The document also introduces notation and provides a proof for a swapping lemma. The given text is a proof of Proposition 1, provided by Valentin Féray and Paul Thévenin. The authors use equations and arguments to demonstrate the convergence in expectation and convergence in probability for multiplicative functions. They acknowledge Svante Janson for pointing out an incomplete proof in their original paper. [Extracted from the article]
- Published
- 2024
- Full Text
- View/download PDF
16. Asymptotic normality of pattern counts in conjugacy classes
- Author
-
Féray, Valentin, primary and Kammoun, Mohamed Slim, additional
- Published
- 2024
- Full Text
- View/download PDF
17. Convergence law for 231-avoiding permutations
- Author
-
Albert, Michael, Bouvel, Mathilde, Féray, Valentin, Noy, Marc, University of Otago [Dunedin, Nouvelle-Zélande], Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Universitat Politècnica de Catalunya [Barcelona] (UPC), and VF is partially supported by the Future Leader program of the LUE initiative (Lorraine Université d’Excellence).
- Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,05A16, 60C05 (primary), 03C13 (secondary) ,Probability (math.PR) ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Mathematics - Probability - Abstract
We prove that the class of 231-avoiding permutations satisfies a convergence law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behaviour and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis., Comment: 13 pages
- Published
- 2022
18. Components in Meandric Systems and the Infinite Noodle.
- Author
-
Féray, Valentin and Thévenin, Paul
- Subjects
- *
NOODLES - Abstract
We investigate here the asymptotic behaviour of a large, typical meandric system. More precisely, we show the quenched local convergence of a random uniform meandric system |$\boldsymbol {M}_n$| on |$2n$| points, as |$n \rightarrow \infty $| , towards the infinite noodle introduced by Curien et al. [ 3 ]. As a consequence, denoting by |$cc(\boldsymbol {M}_n)$| the number of connected components of |$\boldsymbol {M}_n$| , we prove the convergence in probability of |$cc(\boldsymbol {M}_n)/n$| to some constant |$\kappa $| , answering a question raised independently by Goulden–Nica–Puder [ 8 ] and Kargin [ 12 ]. This result also provides information on the asymptotic geometry of the Hasse diagram of the lattice of non-crossing partitions. Finally, we obtain expressions of the constant |$\kappa $| as infinite sums over meanders, which allows us to compute upper and lower approximations of |$\kappa $|. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
19. Components in Meandric Systems and the Infinite Noodle
- Author
-
Féray, Valentin, primary and Thévenin, Paul, additional
- Published
- 2022
- Full Text
- View/download PDF
20. Random cographs: Brownian graphon limit and asymptotic degree distribution.
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, Maazoun, Mickaël, and Pierrot, Adeline
- Subjects
ASYMPTOTIC distribution ,RANDOM graphs ,LEBESGUE measure - Abstract
We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence toward a Brownian limiting object in the space of graphons. We then show that the degree of a uniform random vertex in a uniform cograph is of order n, and converges after normalization to the Lebesgue measure on [0,1]. We finally analyze the vertex connectivity (i.e., the minimal number of vertices whose removal disconnects the graph) of random connected cographs, and show that this statistics converges in distribution without renormalization. Unlike for the graphon limit and for the degree of a random vertex, the limiting distribution of the vertex connectivity is different in the labeled and unlabeled settings. Our proofs rely on the classical encoding of cographs via cotrees. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. A logical limit law for 231-avoiding permutations.
- Author
-
Albert, Michael, Bouvel, Mathilde, Féray, Valentin, and Noy, Marc
- Subjects
- *
PERMUTATION groups , *PROBABILITY theory , *MATHEMATICAL bounds , *COMBINATORICS , *MATHEMATICAL singularities - Abstract
We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence Ψ, in the language of two total orders, the probability pn,Ψ that a uniform random 231-avoiding permutation of size n satisfies Ψ admits a limit as n is large. Moreover, we establish two further results about the behavior and value of pn,Ψ: (i) it is either bounded away from 0, or decays exponentially fast; (ii) the set of possible limits is dense in [0, 1]. Our tools come mainly from analytic combinatorics and singularity analysis. [ABSTRACT FROM AUTHOR]
- Published
- 2024
22. Random cographs: Brownian graphon limit and asymptotic degree distribution
- Author
-
Frédérique Bassino, Lucas Gerin, Valentin Féray, Adeline Pierrot, Mathilde Bouvel, Mickaël Maazoun, University of Zurich, Féray, Valentin, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Institut für Mathematik [Zürich], Universität Zürich [Zürich] = University of Zurich (UZH), Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Unité de Mathématiques Pures et Appliquées (UMPA-ENSL), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon), Bioinformatique (LRI) (BioInfo - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Swiss National Science Foundation, undergrant number 200021-17253, ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), and Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)
- Subjects
General Mathematics ,Computer Graphics and Computer ,Asymptotic distribution ,340 Law ,610 Medicine & health ,0102 computer and information sciences ,01 natural sciences ,1704 Computer Graphics and Computer-Aided Design ,Combinatorics ,510 Mathematics ,2604 Applied Mathematics ,Computer Science::Discrete Mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Cograph ,Aided Design ,0101 mathematics ,Brownian motion ,Mathematics ,2600 General Mathematics ,Lebesgue measure ,Degree (graph theory) ,Applied Mathematics ,Probability (math.PR) ,010102 general mathematics ,Brownian excursion ,Degree distribution ,Computer Graphics and Computer-Aided Design ,Vertex (geometry) ,[MATH.MATH-PR]Mathematics [math]/Probability [math.PR] ,1712 Software ,10123 Institute of Mathematics ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,Mathematics - Probability ,Software - Abstract
We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence towards a Brownian limiting object in the space of graphons. We then show that the degree of a uniform random vertex in a uniform cograph is of order $n$, and converges after normalization to the Lebesgue measure on $[0,1]$. We finally analyze the vertex connectivity (i.e. the minimal number of vertices whose removal disconnects the graph) of random connected cographs, and show that this statistics converges in distribution without renormalization. Unlike for the graphon limit and for the degree of a random vertex, the limiting distribution is different in the labeled and unlabeled settings. Our proofs rely on the classical encoding of cographs via cotrees. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis., 36 pages, 6 figures; v3 includes a new reference to Diaconis-Holmes-Janson (arXiv:0908.2448) for the continuity of the degree distribution for graphons
- Published
- 2022
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.