Tata Institute of Fundamental Research
Improved Counting Relative to Pseudorandom Graphs
Seminar
Speaker:
Jozef Skokan (London School of Economics
Department of Mathematics
Houghton Street
London, WC2A 2AE
United Kingdom)
Organiser:
Jaikumar Radhakrishnan
Date:
Thursday, 14 Aug 2014, 10:00 to 11:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
Abstract: A graph is `pseudorandom' if it appears random according to certain statistics. Recently, Conlon, Fox and Zhao proved a counting lemma, counting small graphs in $\varepsilon$-regular subgraphs of sparse pseudorandom graphs. This counting lemma has many important applications such as sparse pseudorandom analogues of Tur\`{a}n’s Theorem, Ramsey’s Theorem and the graph removal lemma.
One key ingredient for the proof of their counting lemma is a regularity inheritance lemma, which states that for most vertices in an $\varepsilon$-regular subgraph of a pseudorandom graph, the neighbourhoods of this vertex form an $\varepsilon’$-regular graph. We improve this regularity inheritance lemma, so that it now applies to graphs with weaker pseudorandomness conditions. This implies an improved counting lemma relative to these pseudorandom graphs (based on joint work with Peter Allen, Julia Boettcher, Maya Stein).
| Speaker: | Jozef Skokan (London School of Economics Department of Mathematics Houghton Street London, WC2A 2AE United Kingdom) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Thursday, 14 Aug 2014, 10:00 to 11:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
Abstract: A graph is `pseudorandom' if it appears random according to certain statistics. Recently, Conlon, Fox and Zhao proved a counting lemma, counting small graphs in $\varepsilon$-regular subgraphs of sparse pseudorandom graphs. This counting lemma has many important applications such as sparse pseudorandom analogues of Tur\`{a}n’s Theorem, Ramsey’s Theorem and the graph removal lemma.
One key ingredient for the proof of their counting lemma is a regularity inheritance lemma, which states that for most vertices in an $\varepsilon$-regular subgraph of a pseudorandom graph, the neighbourhoods of this vertex form an $\varepsilon’$-regular graph. We improve this regularity inheritance lemma, so that it now applies to graphs with weaker pseudorandomness conditions. This implies an improved counting lemma relative to these pseudorandom graphs (based on joint work with Peter Allen, Julia Boettcher, Maya Stein).
One key ingredient for the proof of their counting lemma is a regularity inheritance lemma, which states that for most vertices in an $\varepsilon$-regular subgraph of a pseudorandom graph, the neighbourhoods of this vertex form an $\varepsilon’$-regular graph. We improve this regularity inheritance lemma, so that it now applies to graphs with weaker pseudorandomness conditions. This implies an improved counting lemma relative to these pseudorandom graphs (based on joint work with Peter Allen, Julia Boettcher, Maya Stein).