BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Recently\, Huang proved the Sensitivity Conjecture\, by showin
 g that every set of more than half the vertices of the $d$-dimensional hype
 rcube $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 aske
 d whether similar results can be obtained for other highly symmetric graphs
 . In this lecture we study Huang's question on Cayley graphs of groups.  We
  show that high symmetry alone does not guarantee similar behavior and pres
 ent three infinite families of Cayley graphs of unbounded degree that conta
 in induced subgraphs of maximum degree $1$ on more than half the vertices. 
 In particular\, this refutes a conjecture of Potechin and Tsang\, for which
  first counterexamples were shown recently by Lehner and Verret. The first 
 family consists of dihedrants. The second family are star graphs\, these ar
 e edge-transitive Cayley graphs of the symmetric group. All members of the 
 third family are $d$-regular containing an induced matching on a $\frac{d}{
 2d-1}$-fraction of the vertices. This is largest possible and answers a que
 stion of Lehner and Verret.  On the positive side\, we consider Cayley grap
 hs of Coxeter groups\, where a lower bound similar to Huang's can be shown.
  A generalization of the construction of Chung\, F\"uredi\, Graham\, and Se
 ymour shows that this bound is tight for products of Coxeter groups of type
  $\mathbf{A_n}$\, $\mathbf{I_n}(2k+1)$\, most exceptional cases and not far
  from optimal in general. Then\, we show that also induced subgraphs on mor
 e than half the vertices of Levi graphs of projective planes and of the Ram
 anujan graphs of Lubotzky\, Phillips\, and Sarnak have unbounded degree. Th
 is yields more classes of Cayley graphs with properties similar to the ones
  provided by Huang's results. However\, in contrast to Coxeter groups these
  graphs have no large subcubes. Joint with Ignacio Garcia-Marco. 
DTSTAMP:20210414T195000
DTSTART:20210426T141500
CLASS:PUBLIC
LOCATION:online\n 
SEQUENCE:0
SUMMARY:Kolja Knauer (Universitat de Barcelona): On sensitivity in Cayley g
 raphs
UID:107776684@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20210426-L-Kna
 uer.html
END:VEVENT
END:VCALENDAR