Agenda
January
-
14:0015:00
We will look at an analogue theorem of the classical Erdős-Pósa Theorem. We prove a $GF(q)$-representable matroid analogue of Robertson and Seymour's theorem that planar graphs have an Erdős-Pósa property. Given a matroid $N$, we prove that for every matroid $M$ with bounded branch width, $M$ either contains $r$ skew copies of $N$, or there is a small perturbation of $M$ that doesn't contain $N$ as a minor.
This is joint work with James Davies and Meike Hatzel.
(Fernanda Rivera Omana) [University of Waterloo]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .EnglishLaBRI/178
February
-
11:0012:00
Jonathan Narboni
Title: Lower Bound for Constant-Size Local Certification
Abstract:
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures.
When it comes to the size of the certification labels, one can identify three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored.
The main contribution of this paper is the first non-trivial lower bound for this low regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k-colorability for k≥3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results.
We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound.
EnglishLaBRI 178 -
14:0015:00
TBA
EnglishLaBRI