<div dir="ltr">This semester, the combinatorics and probability seminar will meet<div>on Thursdays at 4:00PM.</div><div><br></div><div>The first talk will be on January 29:</div><div><br></div><div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13px"><font size="3"><span style="color:rgb(0,0,0);font-family:Tahoma">Yuval Filmus (IAS): </span><span style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif">Triangle-intersecting families of graphs</span></font></div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13px"><span style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif;font-size:10pt"><br></span></div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13px"><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>Simonovits and Sós asked the following question in 1976, prompted by the classical Erdős–Ko–Rado theorem:</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font><br></font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>  How big can a collection of subgraphs of K_n be, if the intersection of any two of them contains a triangle?</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font><br></font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>They conjectured that such a collection can contain at most 1/8 of the graphs. </font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>We prove their conjecture, furthermore identifying the optimal collections (&quot;triangle-juntas&quot;).</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>We also prove a stability result, stating that a collection of measure 1/8-epsilon is O(epsilon)-close to an optimal collection.</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>Our proof technique is spectral and relies on the Lovász theta function.</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font><br></font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>Joint work with David Ellis (Queen Mary&#39;s University of London) and Ehud Friedgut (Weizmann institute).</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><br></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font><br></font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font>  --Dan</font></div><div style="color:rgb(0,0,0);font-family:&#39;Segoe UI&#39;,Helvetica,Arial,sans-serif"><font><br></font></div></div></div></div>