Here is a list of upcoming online seminars in combinatorics, automatically generated from researchseminars.org and a few other calendars available in the iCal format. Please let me know if you find any interesting iCal feed / Google Calendar of the seminars.
You can also find a list of upcoming workshops, conferences, and schools.
Timezone: Korea (KST), UTC/GMT+9.
June 2025
June 20
- 9:00 pm – 10:00 pm
-
[gt.go] – Sometimes Only Fools Get it Right: When Cluster Reduction isn’t Safe par Norbert ZehCluster reduction is a technique that can be used to speed up the construction of phylogenetic networks from sets of trees, or so we thought. Baroni, Semple, and Steel proved that cluster reduction is safe for 2 trees, that is, it preserves the optimality of the constructed network when the input consists of 2 trees. While there are inputs where cluster reduction isn’t applicable, Li and Zeh verified experimentally that on 2-tree inputs, it is the single most important technique for constructing optimal networks efficiently in practice, that not using cluster reduction would be folly. This talk shows cluster reduction isn’t safe for 8 or more trees. It will mention but not prove a number of other results in our paper: cluster reduction isn’t safe for computing an optimal orchard that displays 8 or more trees, cluster reduction is safe for 3 trees, and cluster reduction is safe for computing optimal tree-child networks. What happens with 4-7 trees is an open problem, but our intuition is that cluster reduction stops being safe already for 4 trees. Proving this would require different techniques than the ones we use. In particular, we prove that if there exists a set of t trees that cannot be displayed by a network with at most 2n reticulations, then there exists a set of 2t trees for which cluster reduction fails, but every set of 3 trees can be displayed by a network with at most 2n reticulations.
The second part of the talk focuses on proving that there exists a set of 4 trees that cannot be displayed by a network with at most 2n reticulations, which implies our result that cluster reduction isn’t safe starting with 8 trees. More generally, we show that for t = o(lg n), there exists a set of t trees for which the naïve network that displays these trees and has (t – 1)n reticulations is best possible up to lower order terms. Our result also shows that for t = lg n, there exists a set of t trees that cannot be displayed by a network with o(n lg n) reticulations. This is interesting because Bordewich and Semple showed that there exists even a tree-based network with O(n lg n) reticulations that displays all trees on n leaves. Our result shows that the number of reticulations increases by only a constant factor when going from lg n trees to all trees.
This is joint work with Leo van Iersel, Mark Jones, Kaari Landry, Simone Linz, and Mathias Weller.
[Norbert Zeh] (Dalhousie University)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
Remarks / RemarquesFind all the information of the working group on this web page.Retrouvez toutes les informations du GT sur cette page web.
June 26
- 5:00 pm – 6:00 pm
-
Ugo Giocanti, «Maximal order of planar graphs of small diameter»
The degree diameter problem asks for the maximum number of vertices
n∆,D in a graph of maximum degree ∆ and diameter D. While in general,
the best general upper bound one can hope for n∆,D is O(∆^D), Hell and
Seyffarth (1993) proved that for planar graphs of diameter at most 2, we
have n ≤ \lfloor 3∆/2 \rfloor + 1, and provided constructions attaining this bounds. More generally, Fellows, Hell and Seyffarth (1993) proved that every planar graph
of diameter D has O(∆^(\lfloor D/2 \rfloor)) vertices, and that this bound is asymptotically tight. When D is even, Tischenko (2012) proved an explicit optimal upper bound on the number of vertices of a planar graph with diameter D and
maximum degree ∆ (when ∆ is large enough).
On the other hand, when D = 3, the best general known bounds for planar
graphs are due to Fellows, Hell and Seyffarth (1993) who proved that every
planar graph of diameter at most 3 satisfies n ≤ 8∆ + 12 and constructed
planar graphs of diameter 3 with \lfloor 9∆/2 \rfloor – 3 vertices, and the question of
finding better upper bounds is still open.
We will see in this talk that the lower bound provided by Fellows, Hell
and Seyffarth is asymptotically tight, namely that every planar graph with
diameter at most 3 has at most 9
2 ∆+O(1) vertices. Our proof mostly consists
to a reduction to a special instance of the fractional matching problem in
planar graphs, that we solve optimally.Joint work with Antoine Dailly, Sasha Darmon, Claire Hilaire and Petru
Valicov