BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Łukasz Grabowski (Lancaster) DTSTART:20211110T140000Z DTEND:20211110T150000Z DTSTAMP:20260423T003239Z UID:WCS/37 DESCRIPTION:Title: Dir ected analogues of expander graphs and random compact subsets of $\\mathbb {R}^n$\nby Łukasz Grabowski (Lancaster) as part of Warwick Combinator ics Seminar\n\n\nAbstract\nI will talk about two separate projects. The fi rst one is a joint work with Endre Csoka (published in "Combinatorics\, Pr obability and Computing")\, where we construct "extender" graphs - sparse directed graphs with the property that it is impossible to remove a small amount of edges and obtain a graph which does not have long directed paths (long is $|V|^\\delta$\, where $\\delta>0$ is an absolute constant). Exte nders are a directed analogue of expander graphs\, since the latter ones a re characterised by the property that it is impossible to remove a small a mount of edges and obtain graphs which have small connected components. I' ll discuss some conjectures in circuit complexity which motivated us to in troduce extenders.\n\nThe second project is a joint work with Tomasz Ciesl a (preprint available on arxiv). We construct compacts subsets of $\\mathb b{R}^2$ which are not "domains of expansion"\, which answers a question ab out spectral properties of group actions\, raised by Adrian Ioana.\n\nApar t from the general theme of "expansion"\, both projects are related by the method which is used to construct suitable examples - in both cases the c onstruction is probablistic\, and the required properties follow from entr opy estimates.\n LOCATION:https://researchseminars.org/talk/WCS/37/ END:VEVENT END:VCALENDAR