BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Monadic second order logic can be used to express many classic
 al notions of sets of vertices of a graph as for instance: dominating sets\
 , induced matchings\, perfect codes\, independent sets\, or irredundant set
 s. Bounds on the number of sets of any such family of sets are interesting 
 from a combinatorial point of view and have algorithmic applications. Many 
 such bounds on different families of sets over different classes of graphs 
 are already provided in the literature. In particular\, Rote recently showe
 d that the number of minimal dominating sets in trees of order n is at most
  95^(n/13) and that this bound is asymptotically sharp up to a multiplicati
 ve constant. We build on his work to show that what he did for minimal domi
 nating sets can be done for any family of sets definable by a monadic secon
 d-order formula. I will first illustrate the general technique with a reall
 y simple concrete example ( Dominating independent sets). Then I will expla
 in how to generalize this into a more general technique. I will end my talk
  by mentioning a few of the results obtained with this technique. 
DTSTAMP:20210331T124100
DTSTART:20210426T160000
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Matthieu Rosenfeld (LIRMM): Bounding the number of sets defined by 
 a given MSO formula on trees
UID:107776537@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20210426-C-Rosenfeld.html
END:VEVENT
END:VCALENDAR