Institut de Recherche en Informatique Fondamentale

output

20002026

most citedQuantum attacks on Bitcoin, and how to protect against them

225 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing math.COShow all

57 papers · 1 filter

math.CO2026

Distance statistics of block-weighted planar quadrangulations

Jérémie Bouttier, Emmanuel Guitter, Hugo Manet

We study random planar quadrangulations in which each block -- i.e., each simple (without multiple edges) component -- is assigned a weight $u$ . We derive an explicit expression fo…

math.CO2025

Extension of the Gyárfás-Sumner conjecture to signed graphs

Guillaume Aubian, Allen Ibiapina, Luis Kuffner +4

The balanced chromatic number of a signed graph G is the minimum number of balanced sets that cover all vertices of G. Studying structural conditions which imply bounds on the bala…

math.CO2025

The 3-state Potts model on planar triangulations: explicit algebraic solution

Mireille Bousquet-Mélou, Hadrien Notarantonio

We consider the $3$ -state Potts generating function $T (ν, w)$ of planar triangulations; that is, the bivariate series that counts planar triangulations with vertices coloured in $3$ …

math.CO2025

Homology character of the parabolic coset poset

Theo Douvropoulos, Matthieu Josuat-Vergès

Motivated by the analogy with the Coxeter complex on one side, and parking functions on the other side, we study the poset of parabolic cosets in a finite Coxeter group. We show th…

math.CO2025

The slice decomposition of planar hypermaps

Marie Albenque, Jérémie Bouttier

The slice decomposition is a bijective method for enumerating planar maps (graphs embedded in the sphere) with control over face degrees. In this paper, we extend the slice decompo…

math.CO2025

On core of categorical product of (di)graphs

Reza Naserasr, Cyril Pujol

The core of a graph is the smallest graph (in terms of number of vertices) to which it is homomorphically equivalent. The question of the possible order of the core of the tensor p…

math.CO2025

A new definition for m-Cambrian lattices

Clément Chenevière, Wenjie Fang, Corentin Henriet

The Cambrian lattices, introduced in (Reading, 2006), generalize the Tamari lattice to any choice of Coxeter element in any finite Coxeter group. They are further generalized to th…

math.CO2025

Fractional balanced chromatic number of signed subcubic graphs

Xiaolan Hu, Luis Kuffner, Jiaao Li +4

A signed graph is a pair $(G, σ)$ , where $G$ is a graph and $σ : E (G) \to {-, +}$ , called signature, is an assignment of signs to the edges. Given a signed graph $(G, σ)$ wit…

math.CO2024

From order one catalytic decompositions to context-free specifications: the rewiring bijection

Enrica Duchi, Gilles Schaeffer

A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called combinatorial polynomial equations with one catalytic variable, also…

math.CO2024

Bow Metrics and Hyperbolicity

Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1

A ( $λ, μ$ )-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an $α_{i}$ -metric (which is equivalent to a ( $0, i$ )-bow metric). A graph $G = (V, E)$ is…

math.CO2024

Enumeration of planar bipartite tight irreducible maps

Jérémie Bouttier, Emmanuel Guitter, Hugo Manet

We consider planar bipartite maps which are both tight, i.e. without vertices of degree $1$ , and $2 b$ -irreducible, i.e. such that each cycle has length at least $2 b$ and such that…

math.CO2024

Uniform generation of large traces

Samy Abbes, Vincent Jugé

We introduce an algorithm for the uniform generation of infinite traces, i.e., infinite words up to commutation of some letters. The algorithm outputs on-the-fly approximations of…

math.CO2024

About almost covering subsets of the hypercube

Arijit Ghosh, Chandrima Kayal, Soumi Nandi

Let $F$ be a field, and consider the hypercube ${0, 1}^{n}$ in $F^{n}$ . Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a p…

math.CO2024

A poset-like approach to positive opetopes

Louise Leclerc

We introduce in this paper a new formalisation of positive opetopes where faces are organised in a poset. Then we show that our definition is equivalent to that of positives opetop…

math.CO2024

Obstructions to return preservation for episturmian morphisms

Valérie Berthé, Herman Goulet-Ouellet

This paper studies obstructions to preservation of return sets by episturmian morphisms. We show, by way of an explicit construction, that infinitely many obstructions exist. This…

math.CO2024

Macdonald characters from a new formula for Macdonald polynomials

Houcine Ben Dali, Michele D'Adderio

We introduce a new operator $Γ$ on symmetric functions, which enables us to obtain a creation formula for Macdonald polynomials. This formula provides a connection between the theo…

math.CO2023

Lecture hall graphs and the Askey scheme

Sylvie Corteel, Bhargavi Jonnadula, Jonathan P. Keating +1

We establish, for every family of orthogonal polynomials in the $q$ -Askey scheme and the Askey scheme, a combinatorial model for mixed moments and coefficients in terms of paths…

math.CO2023

Balanced-chromatic number and Hadwiger-like conjectures

Andrea Jiménez, Jessica McDonald, Reza Naserasr +2

Motivated by different characterizations of planar graphs and the 4-Color Theorem, several structural results concerning graphs of high chromatic number have been obtained. Toward…

math.CO2022★ 1 cited

Circular flows in mono-directed signed graphs

Jiaao Li, Reza Naserasr, Zhouningxin Wang +1

In this paper the concept of circular $r$ -flows in a mono-directed signed graph $(G, σ)$ is introduced. That is a pair $(D, f)$ , where $D$ is an orientation on $G$ and $f: E(G)\to…

math.CO2022★ 3 cited

Characterizing and recognizing exact-distance squares of graphs

Yandong Bai, Pedro P. Cortés, Reza Naserasr +1

For a graph $G = (V, E)$ , its exact-distance square, $G^{[♯2]}$ , is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have d…

math.CO2022

The Generalized Cluster Complex: Refined Enumeration of Faces and Related Parking Spaces

Theo Douvropoulos, Matthieu Josuat-Vergès

The generalized cluster complex was introduced by Fomin and Reading, as a natural extension of the Fomin-Zelevinsky cluster complex coming from finite type cluster algebras. In thi…

math.CO2022★ 5 cited

Tiered trees and Theta operators

Michele D'Adderio, Alessandro Iraci, Yvan LeBorgne +2

In [Dugan-Glennon-Gunnells-Steingrimsson-2019], the authors introduce tiered trees to define combinatorial objects counting absolutely indecomposable representations of certain qui…

math.CO2021★ 10 cited

Counting chains in the noncrossing partition lattice via the W-Laplacian

Guillaume Chapuy, Theo Douvropoulos

We give an elementary, case-free, Coxeter-theoretic derivation of the formula $h^{n} n! /∣ W ∣$ for the number of maximal chains in the noncrossing partition lattice $N C (W)$ of a real re…

math.CO2021★ 12 cited

$b$ -monotone Hurwitz numbers: Virasoro constraints, BKP hierarchy, and $O (N)$ -BGW integral

Valentin Bonzom, Guillaume Chapuy, Maciej Dołęga

We study a $b$ -deformation of monotone Hurwitz numbers, obtained by deforming Schur functions into Jack symmetric functions. We give an evolution equation for this model and derive…

Distance statistics of block-weighted planar quadrangulations

Extension of the Gyárfás-Sumner conjecture to signed graphs

The 3-state Potts model on planar triangulations: explicit algebraic solution

Homology character of the parabolic coset poset

The slice decomposition of planar hypermaps

On core of categorical product of (di)graphs

A new definition for m-Cambrian lattices

Fractional balanced chromatic number of signed subcubic graphs

From order one catalytic decompositions to context-free specifications: the rewiring bijection

Bow Metrics and Hyperbolicity

Enumeration of planar bipartite tight irreducible maps

Uniform generation of large traces

About almost covering subsets of the hypercube

A poset-like approach to positive opetopes

Obstructions to return preservation for episturmian morphisms

Macdonald characters from a new formula for Macdonald polynomials

Lecture hall graphs and the Askey scheme

Balanced-chromatic number and Hadwiger-like conjectures

Circular flows in mono-directed signed graphs

Characterizing and recognizing exact-distance squares of graphs

The Generalized Cluster Complex: Refined Enumeration of Faces and Related Parking Spaces

Tiered trees and Theta operators

Counting chains in the noncrossing partition lattice via the W-Laplacian

b-monotone Hurwitz numbers: Virasoro constraints, BKP hierarchy, and O(N)-BGW integral

$b$ -monotone Hurwitz numbers: Virasoro constraints, BKP hierarchy, and $O (N)$ -BGW integral