32 citations · 63 across the 20 of their papers we have counts for
25 papers
The average-case complexity of the Word Problem for groups of matrices over~ is linear
Frédérique Bassino, Cyril Nicaud, Vincent Jugé +1
We show that the Word Problem in finitely generated subgroups of can be solved in linear average-case complexity, both when the input words are chosen u…
Dense and nondense limits for uniform random intersection graphs
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +2
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 f…
Silhouettes and generic properties of subgroups of the modular group
Frédérique Bassino, Cyril Nicaud, Pascal Weil
We show that the probability for a finitely generated subgroup of the modular group, of size , to be almost malnormal or non-parabolic, tends to 0 as tends to infinity -- wh…
Random generation of subgroups of the modular group with a fixed isomorphism type
Frédérique Bassino, Cyril Nicaud, Pascal Weil
We show how to efficiently count and generate uniformly at random finitely generated subgroups of the modular group of a given isomorphism type. The me…
Scaling limit of graph classes through split decomposition
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +2
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:…
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
Frédérique Bassino, Mathilde Bouvel, Michael Drmota +4
This paper is interested in independent sets (or equivalently, cliques) in uniform random cographs. We also study their permutation analogs, namely, increasing subsequences in unif…
Silhouettes and generic properties of subgroups of the modular group
Frédérique Bassino, Cyril Nicaud, Pascal Weil
We show how to count and randomly generate finitely generated subgroups of the modular group of a given isomorphism type. We also prove that almost mal…
Statistics of subgroups of the modular group
Frédérique Bassino, Cyril Nicaud, Pascal Weil
We count the finitely generated subgroups of the modular group . More precisely: each such subgroup can be represented by its Stallings graph …
Random cographs: Brownian graphon limit and asymptotic degree distribution
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +3
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 graphon…
Scaling limits of permutation classes with a finite specification: a dichotomy
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +3
We consider uniform random permutations in classes having a finite combinatorial specification for the substitution decomposition. These classes include (but are not limited to) al…
Universal limits of substitution-closed permutation classes
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +3
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 serie…
Random presentations and random subgroups: a survey
Frédérique Bassino, Cyril Nicaud, Pascal Weil
This is a survey of results on random group presentations, and on random subgroups of certain fixed groups. Being a survey, this paper does not contain new results, but it offers a…
The Brownian limit of separable permutations
Frédérique Bassino, Mathilde Bouvel, Valentin Féray +2
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…
Generic properties of subgroups of free groups and finite presentations
Frédérique Bassino, Cyril Nicaud, Pascal Weil
Asymptotic properties of finitely generated subgroups of free groups, and of finite group presentations, can be considered in several fashions, depending on the way these objects a…
An algorithm computing combinatorial specifications of permutation classes
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +2
This article presents a methodology that automatically derives a combinatorial specification for a permutation class C, given its basis B of excluded patterns and the set of simple…
On the genericity of Whitehead minimality
Frédérique Bassino, Cyril Nicaud, Pascal Weil
We show that a finitely generated subgroup of a free group, chosen uniformly at random, is strictly Whitehead minimal with overwhelming probability. Whitehead minimality is one of…
Linear-time generation of specifiable combinatorial structures: general theory and first examples
Frederique Bassino, Andrea Sportiello
Various specifiable combinatorial structures, with d extensive parameters, can be exactly sampled both by the recursive method, with linear arithmetic complexity if a heavy preproc…
An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +1
In this article, we describe an algorithm to determine whether a permutation class C given by a finite basis B of excluded patterns contains a finite number of simple permutations.…
Combinatorial specification of permutation classes
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +2
This article presents a methodology that automatically derives a combinatorial specification for the permutation class C = Av(B), given its basis B of excluded patterns and the set…
Asymptotic enumeration of Minimal Automata
Frederique Bassino, Julien David, Andrea Sportiello
We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over t…
Optimal prefix codes for pairs of geometrically-distributed random variables
Frédérique Bassino, Julien Clément, Gadiel Seroussi +1
Optimal prefix codes are studied for pairs of independent, integer-valued symbols emitted by a source with a geometric probability distribution of parameter , . By en…
Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot +1
We present an algorithm running in time O(n ln n) which decides if a wreath-closed permutation class Av(B) given by its finite basis B contains a finite number of simple permutatio…
Statistical properties of subgroups of free groups
Frédérique Bassino, Armando Martino, Cyril Nicaud +2
The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based…
On the Average Complexity of Moore's State Minimization Algorithm
Frédérique Bassino, Julien David, Cyril Nicaud
We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with n states, the average complexity of Moore's state…