You are cordially invited to our next Monday Lecture &
Colloquium on April 26th at 14:15 h & 16:00 h, online via
Zoom. Invitation link: Zoom - Invitation Time: Monday, April 26th - 14:15 h Lecture: Kolja Knauer (Universitat de Barcelona) Title: On sensitivity in Cayley graphs Abstract:Recently, Huang proved the Sensitivity Conjecture, by showing
that every set of more than half the vertices of the
$d$-dimensional hypercube $Q_d$ induces a subgraph of maximum
degree at least $\sqrt{d}$. This is tight by a result of Chung,
F\"uredi, Graham, and Seymour. Huang asked whether similar
results can be obtained for other highly symmetric graphs. In
this lecture we study Huang's question on Cayley graphs of
groups.
Time: Monday, April 26th - 16:00 h s.t. Colloquium: Matthieu Rosenfeld (LIRMM) Title: Bounding the number of sets defined by a given MSO formula on trees Abstract:Monadic second
order logic can be used to express many classical notions of sets
of vertices of a graph as for instance: dominating sets, induced
matchings, perfect codes, independent sets, or irredundant sets.
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 showed 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
multiplicative constant. We build on his work to show that what he
did for minimal dominating sets can be done for any family of sets
definable by a monadic second-order formula.
I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain 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. |