225 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. Random generation and scaling limits of fixed genus factorizations into transpositions
- Author
-
Féray, Valentin, Louf, Baptiste, and Thévenin, Paul
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05A05, 05C10, 05C80 - Abstract
We study the asymptotic behaviour of random factorizations of the $n$-cycle into transpositions of fixed genus $g>0$. They have a geometric interpretation as branched covers of the sphere and their enumeration as Hurwitz numbers was extensively studied in algebraic combinatorics and enumerative geometry. On the probabilistic side, several models and properties of permutation factorizations were studied in previous works, in particular minimal factorizations of cycles into transpositions (which corresponds to the case $g=0$ of this work). Using the representation of factorizations via unicellular maps, we first exhibit an algorithm which samples an asymptotically uniform factorization of genus $g$ in linear time. In a second time, we code a factorization as a process of chords appearing one by one in the unit disk, and we prove the convergence (as $n\to\infty$) of the process associated with a uniform genus $g$ factorization of the $n$-cycle. The limit process can be explicitly constructed from a Brownian excursion. Finally, we establish the convergence of a natural genus process, coding the appearance of the successive genera in the factorization., Comment: 62 pages, 17 figures
- Published
- 2021
12. 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
13. 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
Mathematics - Combinatorics ,Mathematics - Probability ,60C05, 05A05 - 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., Comment: 35 pages, 3 figures, attached python worksheet for the singularity analysis computation. v3: presentation improved, following referee's suggestions, use of journal layout
- Published
- 2021
- Full Text
- View/download PDF
14. 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
15. A positivity conjecture on the structure constants of shifted Jack functions
- Author
-
Alexandersson, Per and Féray, Valentin
- Subjects
Mathematics - Combinatorics - Abstract
We consider Jack polynomials $J_\lambda$ and their shifted analogue $J^#_\lambda$. In 1989, Stanley conjectured that $\langle J_\mu J_\nu, J_\lambda \rangle$ is a polynomial with nonnegative coefficients in the parameter $\alpha$. In this note, we extend this conjecture to the case of shifted Jack polynomials., Comment: 9 pages, the main contribution is a conjecture with supporting numerical data; comments or solutions welcome!
- Published
- 2019
16. On the central limit theorem for the two-sided descent statistics in Coxeter groups
- Author
-
Féray, Valentin
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 60F05, 05E15 - Abstract
In 2018, Kahle and Stump raised the following problem: identify sequences of finite Coxeter groups $W_n$ for which the two-sided descent statistics on a uniform random element of $W_n$ is asymptotically normal. Recently, Br\"uck and R\"ottger provided an almost-complete answer, assuming some regularity condition on the sequence $W_n$. In this note, we provide a shorter proof of their result, which does not require any regularity condition. The main new proof ingredient is the use of the second Wasserstein distance on probability distributions, based on the work of Mallows (1972)., Comment: 7 pages; v2, includes a short appendix with basic definitions on Coxeter groups
- Published
- 2019
17. 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
Mathematics - Combinatorics ,Mathematics - Probability - 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., Comment: 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
- 2019
18. A decorated tree approach to random permutations in substitution-closed classes
- Author
-
Borga, Jacopo, Bouvel, Mathilde, Féray, Valentin, and Stufler, Benedikt
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
We establish a novel bijective encoding that represents permutations as forests of decorated (or enriched) trees. This allows us to prove local convergence of uniform random permutations from substitution-closed classes satisfying a criticality constraint. It also enables us to reprove and strengthen permuton limits for these classes in a new way, that uses a semi-local version of Aldous' skeleton decomposition for size-constrained Galton--Watson trees., Comment: New version including referee's corrections, accepted for publication in Electronic Journal of Probability
- Published
- 2019
- Full Text
- View/download PDF
19. 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
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05A05 - Abstract
We consider uniform random permutations in classes having a finite combinatorial specification for the substitution decomposition. These classes include (but are not limited to) all permutation classes with a finite number of simple permutations. Our goal is to study their limiting behavior in the sense of permutons. The limit depends on the structure of the specification restricted to families with the largest growth rate. When it is strongly connected, two cases occur. If the associated system of equations is linear, the limiting permuton is a deterministic $X$-shape. Otherwise, the limiting permuton is the Brownian separable permuton, a random object that already appeared as the limit of most substitution-closed permutation classes, among which the separable permutations. Moreover these results can be combined to study some non strongly connected cases. To prove our result, we use a characterization of the convergence of random permutons by the convergence of random subpermutations. Key steps are the combinatorial study, via substitution trees, of families of permutations with marked elements inducing a given pattern, and the singularity analysis of the corresponding generating functions., Comment: 72 pages, 27 figures; v4, improved presentation, for journal submission
- Published
- 2019
20. Central limit theorems for patterns in multiset permutations and set partitions
- Author
-
Féray, Valentin
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability - Abstract
We use the recently developed method of weighted dependency graphs to prove central limit theorems for the number of occurrences of any fixed pattern in multiset permutations and in set partitions. This generalizes results for patterns of size 2 in both settings, obtained by Canfield, Janson and Zeilberger and Chern, Diaconis, Kane and Rhoades, respectively., Comment: version 2 (52 pages) implements referee's suggestions and uses journal layout
- Published
- 2018
- Full Text
- View/download PDF
21. Trajectories in random minimal transposition factorizations
- Author
-
Féray, Valentin and Kortchemski, Igor
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05C05, 05A05, 60F17 - Abstract
We study random typical minimal factorizations of the $n$-cycle, which are factorizations of $(1, \ldots,n)$ as a product of $n-1$ transpositions, chosen uniformly at random. Our main result is, roughly speaking, a local convergence theorem for the trajectories of finitely many points in the factorization. The main tool is an encoding of the factorization by an edge and vertex-labelled tree, which is shown to converge to Kesten's infinite Bienaym\'e-Galton-Watson tree with Poisson offspring distribution, uniform i.i.d. edge labels and vertex labels obtained by a local exploration algorithm., Comment: contains 28 pages, 8 figures, incorporates referee's suggestion and uses journal formatting
- Published
- 2018
22. Two first-order logics of permutations
- Author
-
Albert, Michael, Bouvel, Mathilde, and Féray, Valentin
- Subjects
Mathematics - Combinatorics ,Mathematics - Logic - Abstract
We consider two orthogonal points of view on finite permutations, seen as pairs of linear orders (corresponding to the usual one line representation of permutations as words) or seen as bijections (corresponding to the algebraic point of view). For each of them, we define a corresponding first-order logical theory, that we call $\mathsf{TOTO}$ (Theory Of Two Orders) and $\mathsf{TOOB}$ (Theory Of One Bijection) respectively. We consider various expressibility questions in these theories. Our main results go in three different direction. First, we prove that, for all $k \ge 1$, the set of $k$-stack sortable permutations in the sense of West is expressible in $\mathsf{TOTO}$, and that a logical sentence describing this set can be obtained automatically. Previously, descriptions of this set were only known for $k \le 3$. Next, we characterize permutation classes inside which it is possible to express in $\mathsf{TOTO}$ that some given points form a cycle. Lastly, we show that sets of permutations that can be described both in $\mathsf{TOOB}$ and $\mathsf{TOTO}$ are in some sense trivial. This gives a mathematical evidence that permutations-as-bijections and permutations-as-words are somewhat different objects., Comment: v2: minor changes, following a referee report
- Published
- 2018
23. 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
24. 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
25. Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
- Author
-
Féray, Valentin, Méliot, Pierre-Loïc, and Nikeghbali, Ashkan
- Subjects
Mathematics - Probability - Abstract
In this paper, we show how to use the framework of mod-Gaussian convergence in order to study the fluctuations of certain models of random graphs, of random permutations and of random integer partitions. We prove that, in these three frameworks, a generic homogeneous observable of a generic random model is mod-Gaussian under an appropriate renormalisation. This implies a central limit theorem with an extended zone of normality, a moderate deviation principle, an estimate of the speed of convergence, a local limit theorem and a concentration inequality. The universal asymptotic behavior of the observables of these models gives rise to a notion of mod-Gaussian moduli space., Comment: New version: the paper has been slightly shortened, and a few references were added. 52 pages, 13 figures
- Published
- 2017
- Full Text
- View/download PDF
26. The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
- Author
-
Féray, Valentin and Kortchemski, Igor
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
We study random typical minimal factorizations of the $n$-cycle into transpositions, which are factorizations of $(1, \ldots,n)$ as a product of $n-1$ transpositions. By viewing transpositions as chords of the unit disk and by reading them one after the other, one obtains a sequence of increasing laminations of the unit disk (i.e. compact subsets of the unit disk made of non-intersecting chords). When an order of $\sqrt{n}$ consecutive transpositions have been read, we establish, roughly speaking, that a phase transition occurs and that the associated laminations converge to a new one-parameter family of random laminations, constructed from excursions of specific L\'evy processes. Our main tools involve coding random minimal factorizations by conditioned two-type Bienaym\'e--Galton--Watson trees. We establish in particular limit theorems for two-type BGW trees conditioned on having given numbers of vertices of both types, and with an offspring distribution depending on the conditioning size. We believe that this could be of independent interest., Comment: 78 pages, 14 figures, 1 animation. Final version: title changed, to appear in Annales Henri Lebesgue
- Published
- 2017
27. Asymptotics for skew standard Young tableaux via bounds for characters
- Author
-
Dousse, Jehanne and Féray, Valentin
- Subjects
Mathematics - Combinatorics ,05A16, 05E05, 05E10 - Abstract
We are interested in the asymptotics of the number of standard Young tableaux $f^{\lambda/\mu}$ of a given skew shape $\lambda/\mu$. We mainly restrict ourselves to the case where both diagrams are balanced, but investigate all growth regimes of $|\mu|$ compared to $|\lambda|$, from $|\mu|$ fixed to $|\mu|$ of order $|\lambda|$. When $|\mu|=o(|\lambda|^{1/3})$, we get an asymptotic expansion to any order. When $|\mu|=o(|\lambda|^{1/2})$, we get a sharp upper bound. For bigger $|\mu|$, we prove a weaker bound and give a conjecture on what we believe to be the correct order of magnitude. Our results are obtained by expressing $f^{\lambda/\mu}$ in terms of irreducible character values of the symmetric group and applying known upper bounds on characters., Comment: 15 pages, v3: final version incorporating referee comments
- Published
- 2017
28. Universal limits of substitution-closed permutation classes
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, Maazoun, Mickaël, and Pierrot, Adeline
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05A05 - Abstract
We consider uniform random permutations in proper substitution-closed classes and study their limiting behavior in the sense of permutons. The limit depends on the generating series of the simple permutations in the class. Under a mild sufficient condition, the limit is an elementary one-parameter deformation of the limit of uniform separable permutations, previously identified as the Brownian separable permuton. This limiting object is therefore in some sense universal. We identify two other regimes with different limiting objects. The first one is degenerate; the second one is nontrivial and related to stable trees. These results are obtained thanks to a characterization of the convergence of random permutons through the convergence of their expected pattern densities. The limit of expected pattern densities is then computed by using the substitution tree encoding of permutations and performing singularity analysis on the tree series., Comment: 73 pages, 17 figures
- Published
- 2017
- Full Text
- View/download PDF
29. Mod-$\phi$ convergence, II: Estimates on the speed of convergence
- Author
-
Féray, Valentin, Méliot, Pierre-Loïc, and Nikeghbali, Ashkan
- Subjects
Mathematics - Probability - Abstract
In this paper, we give estimates for the speed of convergence towards a limiting stable law in the recently introduced setting of mod-$\phi$ convergence. Namely, we define a notion of zone of control, closely related to mod-$\phi$ convergence, and we prove estimates of Berry-Esseen type under this hypothesis. Applications include: the winding number of a planar Brownian motion; classical approximations of stable laws by compound Poisson laws; examples stemming from determinantal point processes (characteristic polynomials of random matrices and zeroes of random analytic functions); sums of variables with an underlying dependency graph (for which we recover a result of Rinott, obtained by Stein's method); the magnetization in the $d$-dimensional Ising model; and functionals of Markov chains., Comment: 53 pages, 11 figures. V2: minor modifications, according to referee's comments
- Published
- 2017
30. 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
31. Weighted dependency graphs and the Ising model
- Author
-
Dousse, Jehanne and Féray, Valentin
- Subjects
Mathematics - Probability ,Mathematical Physics ,Mathematics - Combinatorics ,82B20, 60F05 - Abstract
Weighted dependency graphs have been recently introduced by the second author, as a toolbox to prove central limit theorems. In this paper, we prove that spins in the $d$-dimensional Ising model display such a weighted dependency structure. We use this to obtain various central limit theorems for the number of occurrences of local and global patterns in a growing box., Comment: 24 pages, 1 figure, version 2 contains new results
- Published
- 2016
32. Shifted symmetric functions and multirectangular coordinates of Young diagrams
- Author
-
Alexandersson, Per and Féray, Valentin
- Subjects
Mathematics - Combinatorics ,Mathematics - Representation Theory ,Primary: 05E05, Secondary: 20C30 - Abstract
In this paper, we study shifted Schur functions $S_\mu^\star$, as well as a new family of shifted symmetric functions $\mathfrak{K}_\mu$ linked to Kostka numbers. We prove that both are polynomials in multi-rectangular coordinates, with nonnegative coefficients when written in terms of falling factorials. We then propose a conjectural generalization to the Jack setting. This conjecture is a lifting of Knop and Sahi's positivity result for usual Jack polynomials and resembles recent conjectures of Lassalle. We prove our conjecture for one-part partitions., Comment: 2nd version: minor modifications after referee comments
- Published
- 2016
- Full Text
- View/download PDF
33. 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
34. CENTRAL LIMIT THEOREMS FOR PATTERNS IN MULTISET PERMUTATIONS AND SET PARTITIONS
- Author
-
Féray, Valentin
- Published
- 2020
35. Weighted dependency graphs
- Author
-
Féray, Valentin
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60F05, 60C05 (Primary), 05C80, 60K35, 60J10 (Secondary) - Abstract
The theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. In this article, we introduce a more general notion of weighted dependency graphs and give normality criteria in this context. We also provide generic tools to prove that some weighted graph is a weighted dependency graph for a given family of random variables. To illustrate the power of the theory, we give applications to the following objects: uniform random pair partitions, the random graph model $G(n,M)$, uniform random permutations, the symmetric simple exclusion process and multilinear statistics on Markov chains. The application to random permutations gives a bivariate extension of a functional central limit theorem of Janson and Barbour. On Markov chains, we answer positively an open question of Bourdon and Vall\'ee on the asymptotic normality of subword counts in random texts generated by a Markovian source., Comment: 57 pages. Third version: minor modifications, after review process
- Published
- 2016
36. The Brownian limit of separable permutations
- Author
-
Bassino, Frédérique, Bouvel, Mathilde, Féray, Valentin, Gerin, Lucas, and Pierrot, Adeline
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05 (primary), 05A05 (secondary) - Abstract
We study random uniform permutations in an important class of pattern-avoiding permutations: the separable permutations. We describe the asymptotics of the number of occurrences of any fixed given pattern in such a random permutation in terms of the Brownian excursion. In the recent terminology of permutons, our work can be interpreted as the convergence of uniform random separable permutations towards a "Brownian separable permuton"., Comment: 45 pages, 14 figures, incorporating referee's suggestions
- Published
- 2016
37. Cumulants of Jack symmetric functions and $b$-conjecture
- Author
-
Dołęga, Maciej and Féray, Valentin
- Subjects
Mathematics - Combinatorics ,05E05 - Abstract
Goulden and Jackson (1996) introduced, using Jack symmetric functions, some multivariate generating series $\psi(x, y, z; t, 1+\beta)$ that might be interpreted as a continuous deformation of the generating series of rooted hypermaps. They made the following conjecture: the coefficients of $\psi(x, y, z; t, 1+\beta)$ in the power-sum basis are polynomials in $\beta$ with nonnegative integer coefficients (by construction, these coefficients are rational functions in $\beta$). We prove partially this conjecture, nowadays called $b$-conjecture, by showing that coefficients of $\psi(x, y, z; t, 1+ \beta)$ are polynomials in $\beta$ with rational coefficients. A key step of the proof is a strong factorization property of Jack polynomials when the Jack-deformation parameter $\alpha$ tends to $0$, that may be of independent interest., Comment: 27 pages, 2 figures, to appear in Trans. Amer. Math. Soc
- Published
- 2016
- Full Text
- View/download PDF
38. On the combinatorial local log-concavity conjecture and a result of Stanley
- Author
-
Féray, Valentin
- Subjects
Mathematics - Combinatorics - Abstract
The purpose of this note is to explain that the combinatorial local log-concavity conjecture introduced by Gross, Mansour, Tucker and Wang (Eur. J. Comb. 52, 207-222, 2016) in fact follows from a result of Stanley (Eur. J. Comb. 32 (6), 937-943, 2011)., Comment: 2 pages
- Published
- 2015
39. Cyclic inclusion-exclusion
- Author
-
Féray, Valentin
- Subjects
Mathematics - Combinatorics ,06A07, 05E05 - Abstract
Following the lead of Stanley and Gessel, we consider a morphism which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as multivariate generating series of non-decreasing functions on the graph. We describe the kernel of this morphism, using a simple combinatorial operation that we call cyclic inclusion-exclusion. Our result also holds for the natural noncommutative analog and for the commutative and noncommutative restrictions to bipartite graphs. An application to the theory of Kerov character polynomials is given., Comment: comments welcome
- Published
- 2014
40. Mod-ϕ Convergence, II: Estimates on the Speed of Convergence
- Author
-
Féray, Valentin, Méliot, Pierre-Loïc, Nikeghbali, Ashkan, Morel, Jean-Michel, Editor-in-Chief, Teissier, Bernard, Editor-in-Chief, Baur, Karin, Advisory Editor, Brion, Michel, Advisory Editor, De Lellis, Camillo, Advisory Editor, Figalli, Alessio, Advisory Editor, Huber, Annette, Advisory Editor, Khoshnevisan, Davar, Advisory Editor, Kontoyiannis, Ioannis, Advisory Editor, Kunoth, Angela, Advisory Editor, Mézard, Ariane, Advisory Editor, Podolskij, Mark, Advisory Editor, Serfaty, Sylvia, Advisory Editor, Vezzosi, Gabriele, Advisory Editor, Wienhard, Anna, Advisory Editor, Donati-Martin, Catherine, editor, Lejay, Antoine, editor, and Rouault, Alain, editor
- Published
- 2019
- Full Text
- View/download PDF
41. Two first-order logics of permutations
- Author
-
Albert, Michael, Bouvel, Mathilde, and Féray, Valentin
- Published
- 2020
- Full Text
- View/download PDF
42. Super quasi-symmetric functions via Young diagrams
- Author
-
Aval, Jean-Christophe, Féray, Valentin, Novelli, Jean-Christophe, and Thibon, Jean-Yves
- Subjects
Mathematics - Combinatorics ,05E05, 05E10 - Abstract
We consider the multivariate generating series $F_P$ of $P$-partitions in infinitely many variables $x_1, x_2 , \dots$. For some family of ranked posets $P$, it is natural to consider an analog $N_P$ with two infinite alphabets. When we collapse these two alphabets, we trivially recover $F_P$. Our main result is the converse, that is, the explicit construction of a map sending back $F_P$ onto $N_P$. We also give a noncommutative analog of the latter. An application is the construction of a basis of WQSym with a non-negative multiplication table, which lifts a basis of QSym introduced by K. Luoto., Comment: 12 pages, extended abstract of arXiv:1312.2727, presented at FPSAC conference. The presentation of the results is quite different from the long version
- Published
- 2014
43. Gaussian fluctuations of Young diagrams and structure constants of Jack characters
- Author
-
Dołęga, Maciej and Féray, Valentin
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics ,60C05, 05E05 (secondary:60B20) - Abstract
In this paper, we consider a deformation of Plancherel measure linked to Jack polynomials. Our main result is the description of the first and second-order asymptotics of the bulk of a random Young diagram under this distribution, which extends celebrated results of Vershik-Kerov and Logan-Shepp (for the first order asymptotics) and Kerov (for the second order asymptotics). This gives more evidence of the connection with Gaussian $\beta$-ensemble, already suggested by some work of Matsumoto. Our main tool is a polynomiality result for the structure constant of some quantities that we call Jack characters, recently introduced by Lassalle. We believe that this result is also interested in itself and we give several other applications of it., Comment: 71 pages. Minor modifications from version 1. An extended abstract of this work, with significantly fewer results and a different title, is available as arXiv:1201.1806
- Published
- 2014
- Full Text
- View/download PDF
44. Quasi-symmetric functions as polynomial functions on Young diagrams
- Author
-
Aval, Jean-Christophe, Féray, Valentin, Novelli, Jean-Christophe, and Thibon, Jean-Yves
- Subjects
Mathematics - Combinatorics ,05E05, 05E10 - Abstract
We determine the most general form of a smooth function on Young diagrams, that is, a polynomial in the interlacing or multirectangular coordinates whose value depends only on the shape of the diagram. We prove that the algebra of such functions is isomorphic to quasi-symmetric functions, and give a noncommutative analog of this result., Comment: 34 pages, 4 figures, version including minor modifications suggested by referees
- Published
- 2013
45. An edge-weighted hook formula for labelled trees
- Author
-
Féray, Valentin, Goulden, I. P., and Lascoux, A.
- Subjects
Mathematics - Combinatorics ,05A19, 05E10 - Abstract
A number of hook formulas and hook summation formulas have previously appeared, involving various classes of trees. One of these classes of trees is rooted trees with labelled vertices, in which the labels increase along every chain from the root vertex to a leaf. In this paper we give a new hook summation formula for these (unordered increasing) trees, by introducing a new set of indeterminates indexed by pairs of vertices, that we call edge weights. This new result generalizes a previous result by F\'eray and Goulden, that arose in the context of representations of the symmetric group via the study of Kerov's character polynomials. Our proof is by means of a combinatorial bijection that is a generalization of the Pr\"ufer code for labelled trees., Comment: 25 pages, 9 figures. Author-produced copy of the article to appear in Journal of Combinatorics, including referee's suggestions
- Published
- 2013
46. Mod-phi convergence I: Normality zones and precise deviations
- Author
-
Féray, Valentin, Méliot, Pierre-Loïc, and Nikeghbali, Ashkan
- Subjects
Mathematics - Probability ,Mathematics - Combinatorics - Abstract
In this paper, we use the framework of mod-$\phi$ convergence to prove precise large or moderate deviations for quite general sequences of real valued random variables $(X_{n})_{n \in \mathbb{N}}$, which can be lattice or non-lattice distributed. We establish precise estimates of the fluctuations $P[X_{n} \in t_{n}B]$, instead of the usual estimates for the rate of exponential decay $\log( P[X_{n}\in t_{n}B])$. Our approach provides us with a systematic way to characterise the normality zone, that is the zone in which the Gaussian approximation for the tails is still valid. Besides, the residue function measures the extent to which this approximation fails to hold at the edge of the normality zone. The first sections of the article are devoted to a proof of these abstract results and comparisons with existing results. We then propose new examples covered by this theory and coming from various areas of mathematics: classical probability theory, number theory (statistics of additive arithmetic functions), combinatorics (statistics of random permutations), random matrix theory (characteristic polynomials of random matrices in compact Lie groups), graph theory (number of subgraphs in a random Erd\H{o}s-R\'enyi graph), and non-commutative probability theory (asymptotics of random character values of symmetric groups). In particular, we complete our theory of precise deviations by a concrete method of cumulants and dependency graphs, which applies to many examples of sums of "weakly dependent" random variables. The large number as well as the variety of examples hint at a universality class for second order fluctuations., Comment: 103 pages. New (final) version: multiple small improvements ; a new section on mod-Gaussian convergence coming from the factorization of the generating function ; the multi-dimensional results have been moved to a forthcoming paper ; and the introduction has been reworked
- Published
- 2013
- Full Text
- View/download PDF
47. Jack polynomials and orientability generating series of maps
- Author
-
Dołęga, Maciej, Féray, Valentin, and Śniady, Piotr
- Subjects
Mathematics - Combinatorics ,05E05 (Primary), 05C10, 05C30, 20C30 (Secondary) - Abstract
We study Jack characters, which are the coefficients of the power-sum expansion of Jack symmetric functions with a suitable normalization. These quantities have been introduced by Lassalle who formulated some challenging conjectures about them. We conjecture existence of a weight on non-oriented maps (i.e., graphs drawn on non-oriented surfaces) which allows to express any given Jack character as a weighted sum of some simple functions indexed by maps. We provide a candidate for this weight which gives a positive answer to our conjecture in some, but unfortunately not all, cases. In particular, it gives a positive answer for Jack characters specialized on Young diagrams of rectangular shape. This candidate weight attempts to measure, in a sense, the non-orientability of a given map., Comment: v2: change of title, substantial changes of the content v3: substantial changes in the presentation
- Published
- 2013
48. On products of long cycles: short cycle dependence and separation probabilities
- Author
-
Féray, Valentin and Rattan, Amarpreet
- Subjects
Mathematics - Combinatorics - Abstract
We present various results on multiplying cycles in the symmetric group. Our first result is a generalisation of the following theorem of Boccara (1980): the number of ways of writing an odd permutation in the symmetric group on $n$ symbols as a product of an $n$-cycle and an $n-1$-cycle is independent of the permutation chosen. We give a number of different approaches of our generalisation. One partial proof uses an inductive method which we also apply to other problems. In particular, we give a formula for the distribution of the number of cycles over all products of cycles of fixed lengths. Another application is related to the recent notion of separation probabilities for permutations introduced by Bernardi, Du, Morales and Stanley (2014)., Comment: 29 pages. Final version, to appear in Journal of Algebraic Combinatorics
- Published
- 2012
49. A multivariate hook formula for labelled trees
- Author
-
Féray, Valentin and Goulden, I. P.
- Subjects
Mathematics - Combinatorics ,Mathematics - Representation Theory ,05A19, 05E10 - Abstract
Several hook summation formulae for binary trees have appeared recently in the literature. In this paper we present an analogous formula for unordered increasing trees of size r, which involves r parameters. The right-hand side can be written nicely as a product of linear factors. We study two specializations of this new formula, including Cayley's enumeration of trees with respect to vertex degree. We give three proofs of the hook formula. One of these proofs arises somewhat indirectly, from representation theory of the symmetric groups, and in particular uses Kerov's character polynomials. The other proofs are more direct, and of independent interest., Comment: 19 pages, 2 figures. Version 2: minor revision
- Published
- 2012
50. A note on a Cayley graph of S_n
- Author
-
Chapuy, Guillaume and Féray, Valentin
- Subjects
Mathematics - Combinatorics - Abstract
Recently in graph theory several authors have studied the spectrum of the Cayley graph of the symmetric group S_n generated by the transpositions (1, i) for 2 <= i <= n. Several conjectures were made and partial results were obtained. The purpose of this note is to point out that, as mentioned also by P. Renteln, this problem is actually already solved in another context. Indeed it is equivalent to studying the spectrum of so-called Jucys-Murphy elements in the algebra of the symmetric group, which is well understood. The aforementioned conjectures are direct consequences of the existing theory. We also present a related result from P. Biane, giving an asymptotic description of this spectrum. We insist on the fact that this note does not contain any new results, but has only been written to convey the information from the algebraic combinatorics community to graph theorists., Comment: 5 pages, 2 figures
- Published
- 2012
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.