BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:23ae10fb-058b-4ff1-88c3-63226e249e5a
X-WR-CALNAME:[gt.go] -  'Sometimes Only Fools Get it Right: When Cluster Re
 duction isn't Safe' par Norbert Zeh
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20270328T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20241027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20251026T030000
RDATE:20261025T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20250330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20260329T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:23ae10fb-058b-4ff1-88c3-63226e249e5a
DTSTAMP:20260517T165702Z
CLASS:PUBLIC
DESCRIPTION:Cluster reduction is a technique that can be used to speed up t
 he construction of phylogenetic networks from sets of trees\, or so we tho
 ught. Baroni\, Semple\, and Steel proved that cluster reduction is safe fo
 r 2 trees\, that is\, it preserves the optimality of the constructed netwo
 rk when the input consists of 2 trees. While there are inputs where cluste
 r 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 reducti
 on would be folly. This talk shows cluster reduction isn’t safe for 8 or m
 ore 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 clu
 ster reduction is safe for computing optimal tree-child networks. What hap
 pens 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 requir
 e 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 wi
 th at most 2n reticulations\, then there exists a set of 2t trees for whic
 h cluster reduction fails\, but every set of 3 trees can be displayed by a
  network with at most 2n reticulations. \n\nThe second part of the talk fo
 cuses on proving that there exists a set of 4 trees that cannot be display
 ed by a network with at most 2n reticulations\, which implies our result t
 hat cluster reduction isn’t safe starting with 8 trees. More generally\, w
 e 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 S
 emple showed that there exists even a tree-based network with O(n lg n) re
 ticulations that displays all trees on n leaves. Our result shows that the
  number of reticulations increases by only a constant factor when going fr
 om lg n trees to all trees. \n\nThis is joint work with Leo van Iersel\, M
 ark Jones\, Kaari Landry\, Simone Linz\, and Mathias Weller. \n\n\n[Norber
 t Zeh] (Dalhousie University) \n\n\nVérifiez que vous êtes bien inscrits s
 ur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/p
 mwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwi
 ki.php/Equipes/Equipes#membres ] \n\nRemarks / Remarques \n\nFind all the 
 information of the working group on this [ https://graphesetoptimisation.l
 abri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] . \nRetrouvez toutes
  les informations du GT sur cette [ https://graphesetoptimisation.labri.fr
 /pmwiki.php/Groupe/GT | page web ] . \n\n\n\nImport automatique depuis htt
 ps://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics par syn
 c_icals_to_drupal.py pour GT-GO
DTSTART;TZID=Europe/Paris:20250620T140000
DTEND;TZID=Europe/Paris:20250620T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] -  'Sometimes Only Fools Get it Right: When Cluster Reducti
 on isn't Safe' par Norbert Zeh
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
