Jean-Sébastien Sereni
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Jean-Sébastien Sereni has a total of 68 co-authors. Here are the top co-authors by number of shared publications:
- Daniel Kral
Masaryk University
13 shared publications - François Pirot
Department of Mathematics Radboud University Nijmegen Netherlands
9 shared publications - Christian Jean Michel
Theoretical Bioinformatics, ICube, C.N.R.S., University of Strasbourg, Illkirch, France
6 shared publications - Jan Volec
Department of Mathematics Faculty of Nuclear Sciences and Physical Engineering Czech Technical University in Prague Trojanova 13 120 00 Prague Czech Republic
6 shared publications - Ross J. Kang
Korteweg-de Vries Institute for Mathematics University of Amsterdam Netherlands
6 shared publications - Elena Fimmel
Institute of Mathematical Biology, Faculty for Computer Sciences, Mannheim University of Applied Sciences, Mannheim, Germany
4 shared publications
Latest Publications
- 28 March 2022
- Published by Elsevier in BioSystems
- Vol. 217, 104668
Trinucleotide -circular codes II: Biology- 28 March 2022
- Published by Elsevier in BioSystems
- Vol. 217, 104668
Trinucleotide -circular codes II: Biology- 26 March 2022
- Published by Elsevier in BioSystems
- Vol. 217, 104667
Trinucleotide -circular codes I: Theory- 26 March 2022
- Published by Elsevier in BioSystems
- Vol. 217, 104667
Trinucleotide -circular codes I: Theory- Open Access
The minimum number of spanning trees in regular multigraphs I: the odd-degree case
This pre-publication was merged with "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283).The resulting full article has been published in The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) and is also availableon HAL (hal-03860510).Cette prépublication a été fusionnée avec "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283), donnant lieu à un article publié dans The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) et disponibleaussi sur HAL (hal-03860510).
Open AccessThe minimum number of spanning trees in regular multigraphs I: the odd-degree case
This pre-publication was merged with "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283).The resulting full article has been published in The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) and is also availableon HAL (hal-03860510).Cette prépublication a été fusionnée avec "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283), donnant lieu à un article publié dans The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) et disponibleaussi sur HAL (hal-03860510).
- Open Access
Fractional chromatic number, maximum degree and girth
We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of~$\Delta$, and improves it when~$\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of~$\Delta$, we also demonstrate that every graph of girth at least~$7$ and maximum degree~$\Delta$ has fractional chromatic number at most~$1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth~$7$ and maximum degree~$\Delta$ is at most~$\frac{2\Delta+9}{5}$ when~$\Delta \in [3,8]$, at most~$\frac{\Delta+7}{3}$ when~$\Delta \in [8,20]$, at most~$\frac{2\Delta+23}{7}$ when~$\Delta \in [20,48]$, and at most~$\frac{\Delta}{4}+5$ when~$\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree~$\Delta \in \{3,4,5\}$ and girth~$g\in \{6,\dotsc,12\}$, notably~$1/3$ when~$(\Delta,g)=(4,10)$ and~$2/7$ when~$(\Delta,g)=(5,8)$.
Open AccessFractional chromatic number, maximum degree and girth
We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of~$\Delta$, and improves it when~$\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of~$\Delta$, we also demonstrate that every graph of girth at least~$7$ and maximum degree~$\Delta$ has fractional chromatic number at most~$1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth~$7$ and maximum degree~$\Delta$ is at most~$\frac{2\Delta+9}{5}$ when~$\Delta \in [3,8]$, at most~$\frac{\Delta+7}{3}$ when~$\Delta \in [8,20]$, at most~$\frac{2\Delta+23}{7}$ when~$\Delta \in [20,48]$, and at most~$\frac{\Delta}{4}+5$ when~$\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree~$\Delta \in \{3,4,5\}$ and girth~$g\in \{6,\dotsc,12\}$, notably~$1/3$ when~$(\Delta,g)=(4,10)$ and~$2/7$ when~$(\Delta,g)=(5,8)$.
- Open Access
- 2 October 2020
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 27 (4) , P4.9
On Fractional Fragility Rates of Graph Classes
We consider, for every positive integer $a$, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most $1/a$. Among other results, we prove that for every positive integer $a$ and every planar graph $G$, there exists such a probability distribution with the additional property that for any set $X$ in the support of the distribution, the graph $G-X$ has component-size at most $(\Delta(G)-1)^{a+O(\sqrt{a})}$, or treedepth at most $O(a^3\log_2(a))$. We also provide nearly-matching lower bounds.- 2 October 2020
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 27 (4) , P4.9
Open AccessOn Fractional Fragility Rates of Graph Classes
We consider, for every positive integer $a$, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most $1/a$. Among other results, we prove that for every positive integer $a$ and every planar graph $G$, there exists such a probability distribution with the additional property that for any set $X$ in the support of the distribution, the graph $G-X$ has component-size at most $(\Delta(G)-1)^{a+O(\sqrt{a})}$, or treedepth at most $O(a^3\log_2(a))$. We also provide nearly-matching lower bounds. - 4 August 2020
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 82 (8) , 1-34
The Relation Between k-Circularity and Circularity of Codes
A code X is k-circular if any concatenation of at most k words from X, when read on a circle, admits exactly one partition into words from X. It is circular if it is k-circular for every integer k. While it is not a priori clear from the definition, there exists, for every pair \((n,\ell )\), an integer k such that every k-circular \(\ell \)-letter code over an alphabet of cardinality n is circular, and we determine the least such integer k for all values of n and \(\ell \). The k-circular codes may represent an important evolutionary step between the circular codes, such as the comma-free codes, and the genetic code.- 4 August 2020
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 82 (8) , 1-34
The Relation Between k-Circularity and Circularity of Codes
A code X is k-circular if any concatenation of at most k words from X, when read on a circle, admits exactly one partition into words from X. It is circular if it is k-circular for every integer k. While it is not a priori clear from the definition, there exists, for every pair \((n,\ell )\), an integer k such that every k-circular \(\ell \)-letter code over an alphabet of cardinality n is circular, and we determine the least such integer k for all values of n and \(\ell \). The k-circular codes may represent an important evolutionary step between the circular codes, such as the comma-free codes, and the genetic code.- Open Access
An algorithmic framework for colouring locally sparse graphs
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $\Delta$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le \Delta^\frac{2\varepsilon}{1+2\varepsilon}/(\log\Delta)^2$, with $\lfloor(1+\varepsilon)\Delta/\log(\Delta/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.Open AccessAn algorithmic framework for colouring locally sparse graphs
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $\Delta$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le \Delta^\frac{2\varepsilon}{1+2\varepsilon}/(\log\Delta)^2$, with $\lfloor(1+\varepsilon)\Delta/\log(\Delta/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs. - Open Access
Graph structure via local occupancy
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lov\'asz local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
Open AccessGraph structure via local occupancy
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lov\'asz local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
- Open Access
Revisiting a theorem by Folkman on graph colouring
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.Open AccessRevisiting a theorem by Folkman on graph colouring
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number. - Open Access
Bipartite independence number in graphs with bounded maximum degree
Come from teaching and research institutions in France or abroad, or from public or private research centers. L'archive ouverte pluridisciplinaire
Open AccessBipartite independence number in graphs with bounded maximum degree
Come from teaching and research institutions in France or abroad, or from public or private research centers. L'archive ouverte pluridisciplinaire