2021-22 LIMDA Seminar
Date: Tuesday, 28 June, 2022
Time: 11:30 (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: The Kahn-Kalai conjecture on thresholds
Speaker: Patrick Morris (UPC)
Abstract:
Ever since the work of Erdős and Rényi pioneering the study of random graphs, one of the central themes of the subject has been to determine the location of the threshold for certain graph properties; the critical probability at which the property switches from being very unlikely to very likely. For many examples of interest, such as the appearance of (possibly spanning) subgraphs, one can obtain lower bounds on thresholds by running simple expectation calculations. In this reading seminar, we will discuss the recent solution of a surprising conjecture of Kahn and Kalai from 2006, that states that these expectation calculations are actually never far from the truth and that they differ from the true value of the threshold by at most a factor of log n. The conjecture is very general and has many important implications in the study of random graph thresholds.
Until a couple of years ago this conjecture seemed far out of reach and it was not even clear whether one should try to prove it or try to find a counterexample. This makes the solution of this conjecture, posted by Park and Pham in March this year, a truly remarkable result and perhaps even more surprising is that their proof is only 5 pages and, by all accounts, a very elegant argument using no heavy machinery. Although this result came as a huge surprise in the community, it builds on the ideas of several big breakthroughs in recent years. Indeed, in 2019, Frankston, Kahn, Narayanan and Park posted the proof of a fractional version of the Kahn-Kalai conjecture, a weaker form of the conjecture that still has far-reaching implications. In turn, the proof in that paper (now in Annals) adopts ideas of another big breakthrough (also in Annals) to a seemingly unrelated problem known as the Erdős-Rado Sunflower problem.
This talk is a taster session for an upcoming reading seminar where we will look at the remarkable recent proof of the Kahn-Kalai conjecture, due to Park and Pham, and several papers that led to this breakthrough. This seminar is planned to start in September.
Date: Thursday, 2 June, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Perfect codes of circulant graphs of degree $p^l-1$
Speaker: Xiaomeng Wang (Lanzhou University, UPC)
Abstract:
A perfect code in a graph is an independent set $D$ such that every vertex not in $D$ is adjacent to exactly one vertex in $D$. We will review the known results on perfect codes in circulant graphs and present a new characterization on the existence and structure of perfect codes in circulant graphs of degree a power of a prime minus one.
Date: Thursday, 26 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Absolutely maximally entangled states: a combinatorial and geometric view
Speaker: Simeon Ball (UPC)
Abstract:
I will assume no prior knowledge of Hilbert spaces or quantum mechanics. This talk is aimed at researchers in graphs and combinatorial geometry.
In this talk I will briefly explain the concept of entanglement in quantum mechanics and define what is an absolutely maximally entangled state of the Hilbert space $({\mathbb C}^q)^{\otimes n}$. In the qubit case ($q=2$) I will sketch a link between such states and simple graphs and by doing so, we will see that it is not difficult to classify all absolutely maximally entangled states of $({\mathbb C}^2)^{\otimes n}$ that have a stabiliser group.
The case $q>2$ is more complicated as simple graphs can no longer be used to describe the states. We can however, find an equivalence to a set of $n$ lines $\mathcal X$ in the finite projective space PG$(n-1,q)$.
In the case $q=2$ (and for simplicity assuming $n$ is even), it is well known that this set of lines $\mathcal X$ has two properties namely, that every co-dimensional two subspace intersects an even number of lines of $\mathcal X$ and any subset of $\frac{1}{2}n$ lines of $\mathcal X$ span the entire space.
The smallest parameters for which it is not known if there is an absolutely maximally entangled state is the Hilbert space $({\mathbb C}^4)^{\otimes 8}$.
In this talk I will explain ongoing work with Edgar Moreno in which we prove that for $q=4$ an
absolutely maximally entangled state (which has a stabiliser group) is equivalent to a set of lines in a finite projective space with a property similar to that for $q=2$. I will explain how we hope to classify all such sets of lines and thereby determine if there is an absolutely maximally entangled state in the Hilbert space $({\mathbb C}^4)^{\otimes 8}$ or not.
Date: Thursday, 19 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: The Semi-Random Tree Process
Speaker: Sofiya Burova (ENS Lyon)
Abstract:
The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of his choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalised online semi-random models. Then, we analyse a particular instance that shares similar features with the original semi-random graph process and study the hitting times of classical graph properties.
Joint work with Lyuben Lichev.
Date: Thursday, 12 May, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Moore's problem in its bipartite biregular version
Speaker: Gabriela Araujo-Pardo (Instituto de Matemáticas, UNAM)
Abstract:
Date: Thursday, 28 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Optimization, Testing, Learning of Deterministic Finite State Machines
Speaker: Alberto Larrauri (TU Graz)
Abstract:
Finite state machines are a formalism used to describe a wide array of
reactive systems. Among them, finite automata are machines that either
accept or reject each input word. We give an overview of three closely-
linked problems related to deterministic finite automata (DFA):
optimization, testing and learning. In the optimization problem, we are
given a classification of input words and the goal is to obtain a
smallest automaton consistent with that information. In conformance
testing, we begin with a DFA A and a bound k, and we are asked to
produce a small set of words distinguishing A from all other (non-
equivalent) automata containing at most k states. Lastly, in active
learning the task is to infer a model of a black-box automaton through
limited interaction with an oracle called a "minimally adequate
teacher". Finally, we briefly discuss extensions of these problems
where instead of considering a single machine in isolation, we study
multiple ones that interact with each other and showcase some recent
results.
Date: Thursday, 21 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Ramsey Multiplicity and Search Heuristics
Speaker: Christoph Spiegel (Zuse Institute Berlin)
Abstract:
We present several new improved and tight asymptotic bounds relating both to the minimum number of monochromatic cliques contained in any edge-coloring of a complete graph as well as the minimum number of cliques in graphs with bounded independence number. Most notably, we present an improvement in the upper bound of the K4 and K5 Ramsey multiplicity and introduce a notion of off-diagonal Ramsey multiplicity. The upper bounds are established through graph and Cayley graph constructions found through well-established computer search heuristics.
Date: Thursday, 21 Apr, 2022
Time: 17.00h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Stability of Erdős-Ko-Rado Theorems in Circle Geometries
Speaker: Sam Adriaensen (Vrije Universiteit Brussel)
Abstract:
Techniques from algebraic graph theory have proven to be quite powerful in solving combinatorial problems. Especially for solving Erdős-Ko-Rado problems. There, one takes an incidence structure consisting of points and blocks (which are sets consisting of points), and one wonders what the largest families of blocks is such that they have pairwise non-empty intersection. In a lot of cases, the largest families are the trivial ones, where you fix a point and just take all blocks containing this point. In a lot of settings, one can prove that these are the only examples of maximum size, using the Hoffman ratio bound.
Often, the limitations of these techniques are that you can only say something about the intersecting families of maximum size. In this talk I will show that we can do better. The incidence structures under investigation are circle geometries. They are typically constructed by taking a quadratic surface Q in 3-dimensional projective space PG(3,q). The non-trivial plane sections of Q are called circles. The points and blocks of the circle geometries are the points and circles respectively of Q. Using the expander mixing lemma, we cannot only prove that the largest intersecting families are of size q² ± O(q), but that all intersecting families of size 1/√2 q² + O(q) are trivial (i.e. they consist of circles through a fixed point).
Date: Thursday, 7 Apr, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Número Sidon-Ramsey en Z_n
Speaker: Luis Miguel Delgado Ordoñez (Universidad del Cauca)
Abstract:
El problema de los conjuntos de Sidon es un problema clásico en la Teoría Combinatoria de Números, del cual daré una breve introducción. Posteriormente, expondré la versión en coloraciones de dicho problema y explicaré su conexión con el teorema de Rado en la teoría de Ramsey donde apareció el denominado Número Sidon-Ramsey. Finalmente, presentaré los resultados obtenidos en la investigación adelantada del Número de Sidon-Ramsey en grupos cíclicos.
Date: Thursday, 7 Apr, 2022
Time: 17.00h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Construcciones combinatorias de códigos
ortogonales ópticos
Speaker: Hamilton Mauricio Ruiz (Universidad del Cauca)
Abstract:
Los códigos ortogonales ópticos COOs, se definen como un conjunto de secuencias de peso constante con buenas propiedades de autocorrelación y correlación cruzada. Desde su aparición en 1989, varias son las áreas de las matemáticas encargadas de la búsqueda y diseño de construcciones explícitas de COOs, una de ellas es la combinatoria. En esta charla explicaremos algunas herramientas combinatorias utilizadas en la construcción de códigos ortogonales ópticos, especialmente aquellas construcciones que utilizan el concepto de cuadrados latinos mutuamente ortogonales y conjuntos de Sidon modulares.
Date: Thursday, 31 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Schur properties of randomly perturbed sets
Speaker: Patrick Morris (UPC)
Abstract:
A set $A$ of integers is said to be Schur if any two-colouring of $A$ results in monochromatic $x,y$ and $z$ with $x+y=z$. We discuss the following problem: how many random integers from $[n]$ need to be added to some $A\subseteq [n]$ to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when $|A|> \ceil{4n/5}$, no random integers are needed, as $A$ is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers $A\subseteq [n]$, adding $\omega(n^{1/3})$ random integers suffices, noting that this is optimal for sets $A$ with $|A|\leq \ceil{n/2}$.
We close the gap between these two results by showing that if $A\subseteq [n]$ with $|A|=\ceil{n/2}+t<\ceil{4n/5}$, then adding $\omega(\min\{n^{1/3},nt^{-1}\})$ random integers will with high probability result in a set that is Schur. Our result is optimal for all $t$, and we further initiate the study of perturbing sparse sets of integers $A$ by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.
Joint work with Shagnik Das and Charlotte Knierim.
Date: Thursday, 24 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Characterization of the extremal families for the Kruskal-Katona's inequality
Speaker: Lluís Vena (UPC)
Abstract:
Given $S$ a family of sets of size $k$ in $[n]$, its lower shadow $\Delta(S)$ is the family of sets of size $k-1$ which are contained in at least one set of the family. The celebrated Kruskal-Katona theorem gives the minimum size of $\Delta(S)$ in terms of the size of $S$. F\"uredi and Griggs (and M\"ors) showed that the extremal families for this shadow minimization problem in the Boolean lattice are unique for some cardinalities and asked for a general characterization of these extremal families.
In this talk we present a new combinatorial inequality from which yet another simple proof of the Kruskal--Katona theorem can be derived. The inequality can be used to obtain a characterization of the extremal families for this minimization problem, giving an answer to the question of F\"uredi and Griggs. Some known and new additional properties of extremal families can also be easily derived from the inequality.
Join work with Oriol Serra.
Date: Thursday, 17 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Path decompositions of random directed graphs
Speaker: Alberto Espuny (TU Ilmenau)
Abstract:
In this talk we consider the problem of decomposing the edges of a directed graph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph.
The problem of determining the path number is generally NP-hard. However, there is a simple lower bound for the path number of a digraph in terms of its degree sequence, and a conjecture of Alspach, Mason, and Pullman from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular, I will discuss some of the ingredients of a recent result showing that the conjecture holds with high probability for the random directed graph D(n,p) for a large range of p.
This is joint work with Viresh Patel and Fabian Stroh.
Date: Thursday, 10 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Higher sumsets and approximate groups
Speaker: Arindam Biswas (U. of Copenhagen)
Abstract:
Let G be an abelian group and A be any non-empty, finite subset. For the integers, the structure of the higher sumsets mA with $m\geq 1$ was investigated by Nathanson in the 1970s. Recent works of Granville-Walker, Lev, etc. have improved some of the bounds of Nathanson and Granville-Shakan-Walker also investigated higher sumsets in $Z^d$. We will discuss these results and their relationship to approximate groups.
Date: Thursday, 3 Mar, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Marked graphs and the chromatic symmetric function
Speaker: Anna de Mier (UPC)
Abstract:
In the mid 90s Stanley introduced the chromatic symmetric function, a
symmetric function analogue of the chromatic polynomial, and he asked
whether it determines trees up to isomorphism. Motivated by this
question and with the aim of better understanding the chromatic
symmetric function, we introduce a class of marked graphs (that is,
graphs with vertices weighted by elements of a semigroup) and a
polynomial on them defined via deletion-contraction. From this
polynomial, that we call the M-polynomial, one can compute the expansion
of the chromatic symmetric function in terms of the chromatic symmetric
functions of stars (which give rise to a basis for symmetric functions).
We then explain how these results could be used to approach Stanley's
question and carry out the program for trees up to diameter five
satisfying a mild extra condition.
This is joint work with José Aliste-Prieto, Rosa Orellana and José Zamora.
Date: Thursday, 24 Feb, 2022
Time: 16.30h (Barcelona time)
Where: Room C3-005 Campus Nord UPC and Zoom link
Title: Some problems on randomly perturbed graphs
Speaker: Alberto Espuny (TU Ilmenau)
Abstract:
The theory of randomly perturbed graphs has seen tremendous growth in recent years. This theory serves to interpolate between classical results in extremal graph theory and the theory of random graphs. Given some property P that we wish to study (say, the containment of a given spanning structure), the idea is to consider a deterministic graph H which does not satisfy P and a random graph G=G(n,p) which is very unlikely to satisfy P, and study whether the union of H and G will satisfy P. In particular, we aim to obtain the best possible combinations of parameters for H and G that will yield P with high probability.
Date: Wednesday, 26 Jan, 2022
Time: 14.30h (Barcelona time)
Where: G-meet: meet.google.com/fty-utgm-qxq
Title: Probabilistic and Extremal studies in Additive Combinatorics
Speaker: Max Wötzel (UPC)
Ph.D. defence, Thesis director: Rué, Juanjo | Serra, Oriol
Abstract:
The results in this thesis concern extremal and probabilistic topics in number theoretic settings. We prove sufficient conditions on when certain types of integer solutions to linear systems of equations in binomial random sets are distributed normally, results on the typical approximate structure of pairs of integer subsets with a given sumset cardinality, as well as upper bounds on how large a family of integer sets defining pairwise distinct sumsets can be. In order to prove the typical structural result on pairs of integer sets, we also establish a new multipartite version of the method of hypergraph containers, generalizing earlier work by Morris, Saxton and Samotij.
Date: Monday, 20 Dec, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Deviation Probabilities for arithmetic progressions
Speaker: Oriol Serra (UPC)
Abstract:
The study of large deviations on the expected number of arithmetic
progressions on a random set of the first N positive integers has a rich
history, parallel to the study of large deviations on subgraph counts of
the random graph G(n,p).
Goldsmith, Griffiths and Scott introduced a new approach using
martingale methods to analyze moderate deviations in subgraph counts in
G(n,m). In the talk an adaption of the method to count arithmetic
structures given by solutions of a linear system in an abelian group is
presented. The method reduces to the general problem of counting edges
in random hypergraphs. Exponential bounds for moderate deviations in
edge counting are then translated to the arithmetic setting. The bounds
for the counting of edges in hypergraphs are seen to be essentially best
possible.
Joint work with Gonzalo Fiz-Pontiveros, Simon Griffiths and Mattheus Secco
Date: Monday, 13 Dec, 2021
Time: 14.00h (Barcelona time)
Where: online at https://meet.google.com/uve-zvxj-wdr
Title: Threshold phenomena involving the connected components of random graphs and digraphs
PhD Defense COULSON, MATTHEW JOHN
Advisor: PERARNAU LLOBET, GUILLEM
Speaker: Mathew Coulson (UPC)
Abstract:
We consider some models of random graphs and directed graphs and investigate their behavior near thresholds for the appearance of certain types of connected components. Firstly, we look at the critical window for the appearance of a giant strongly connected component in binomial random digraphs. We provide bounds on the probability that the largest strongly connected component is very large or very small. Next, we study the configuration model for graphs and show new upper bounds on the size of the largest connected component in the subcritical and barely subcritical regimes. We also show that these bounds are tight in some instances. Finally we look at the configuration model for random digraphs. We investigate the barely sub-critical region and show that this model behaves similarly to the binomial random digraph whose barely sub- and super-critical behaviour was studied by Luczak and Seierstad. Moreover, we show the existence of a threshold for the existence of a giant weak component, as predicted by Kryven.
Date: Monday, 29 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Four families of polynomials in spectral graph theory
Speaker: Miquel Àngel Fiol (UPC)
Abstract:
In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.
Date: Wednesday, 24 Nov, 2021
Time: 15.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Roberto Imbuzeiro Oliveira (IMPA)
Link: https://randnet.upc.edu/seminar/
Date: Monday, 22 Nov, 2021
Time: 14.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Hermitian self-orthogonal codes
Speaker: Simeon Ball (UPC)
Abstract:
Let $C$ be a $[n,k]_{q^2}$ linear code, i.e. a $k$-dimensional subspace of ${\mathbb F}_{q^2}^n$.
$C$ is linearly equivalent to a Hermitian self-orthogonal code if and only if there are non-zero $\lambda_i \in {\mathbb F}_{q}$ such that $$\sum_{i=1}^n \lambda_{i} u_{i}v_{i}^q=0,$$ for all $u,v \in C$.
For any linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$, Rains defined the {\em puncture code} $P(C)$ to be $$P(C)=\{\lambda=(\lambda_{1},\ldots,\lambda_n) \in {\mathbb F}_q^n \ | \ \sum_{{i}=1}^n \lambda_{i} u_{i}v_{i}^q=0, \ \mathrm{for} \ \mathrm{all} \ u,v \in C \}.$$
There is a truncation of a linear code $C$ over ${\mathbb F}_{q^2}$ of length $n$ to a linear over ${\mathbb F}_{q^2}$ of length $r \leqslant n$ which is linearly equivalent to a Hermitian self-orthogonal code if and only if there is an element of $P(C)$ of weight $r$.
Rains was motivated to look for Hermitian self-orthogonal codes, since there is a simple way to construct a $ [\![ n,n-2k]\!] _q$ quantum code, given a Hermitian self-orthogonal code. This construction is due to Ketkar et al, generalising the ${\mathbb F}_4$-construction of Calderbank et al.
In this talk, I will detail an effective way to calculate the puncture code. I will outline how to prove various results about when a linear code has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code and how to extend it to one that does in the case that it has no such truncation. In the case that the code is a Reed-Solomon code, it turns out that the existence of such a truncation of length $r$ is equivalent to the existence of a polynomial $g(X)$ of degree at most $(q-k)q-1$ with the property that $g(X)+g(X)^q$ has $q^2-r$ distinct zeros.
(joint work with Ricard Vilar)
Date: Monday, 15 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: Counting rooted 3-connected bipartite planar maps
Speaker: Marc Noy (UPC)
Abstract:
We provide the first solution to the problem of counting (rooted) 3-connected bipartite planar maps. Our starting point is the enumeration of bicolored planar maps by number of monochromatic edges, following the work of Bernardi and Bousquet-Mélou in J. Comb. Theory Ser. B, 101 (2011), 315--377. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicolored maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form g^n/n^(5/2), where g = 1/r = 2.40958 and r is an explicit algebraic number of degree 10.
This is joint work in progress with Clément Requilé and Juanjo Rué.
Date: Monday, 8 Nov, 2021
Time: 15.00h (Barcelona time)
Where: Room C3001 Campus Nord UPC
Title: On a notion of homomorphisms for graphs embedded on surfaces, and its poset of cores
Speaker: Lluís Vena (UPC)
Abstract: A graph homomorphism between two graphs is a mapping between the corresponding vertex sets that sends edges to edges. We present a homomorphism notion between graphs embedded on (non-necessarily orientable) surfaces, also known as maps, that is graph homomorphism between graphs, yet it preserves the topology they are embedded in (namely its sign genus). Furthermore, we define a core of a map in an analogous way as for graphs, give a characterization of when a map is a core (in terms of the contractible cycles of the map), and we study the properties of the poset of cores, showing that it behaves radically different than in the case of graphs (for instance, there is no dense totally ordered interval).
Joint work with Delia Garijo and Andrew Goodall.
Date: Wednesday, 27 Oct, 2021
Time: 14.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Martin Balko (Charles University Prague)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 29 Sep, 2021
Time: 16.00h (Barcelona time)
Title: RandNET Seminar
Speaker: Louigi Addario-Berry (McGill University)
Link: https://randnet.upc.edu/seminar/
Date: Wednesday, 15 Sep, 2021
Time: 15.00h (Barcelona time) (Watch out: exceptional time)
Where: Room C3005 Campus Nord UPC and Zoom
Title: (Maximal) Independet Sets in Various Random Graph Classes
Speaker: Michael Drmota (TU Wien)
Abstract:
The purpose ot this talk is to discuss the following two questions for
random series-parallel graphs and random co-graphs:
- How many (maximal) independent sets can we expect for a typical graph of this kind?
- Does there typically exist an independent set of linear size?
Interestingly, in both graph classes we can expect exponentially many independent sets,
whereas independent sets of linear size exist typically only for series-parallel graphs.
This talk is based on the following two papers:
M. Drmota, L. Ramos, C. Requile, and J. Rue, Maximal independent sets and maximal matchings in series-parallel and related graph classes, The Electronic Journal of Combinatorics 27 (1), P1.5, 2020.
Frédérique Bassino, Mathilde Bouvel, Michael Drmota, Valentin Féray, Lucas Gerin, Mickaël Maazoun, Adeline Pierrot, Linear-sized independent sets in random cographs and increasing subsequences in separable permutations, arXiv:2104.07444.
Share: