representation for discrete signals that are perfectly timelimited and
nearly bandlimited. Due to the high computational complexity of
projecting onto the DPSS basis - also known as the Slepian basis - this
representation is often overlooked in favor of the fast Fourier
transform (FFT). In this talk I will describe novel fast algorithms for
computing approximate projections onto the leading Slepian basis
elements with a complexity comparable to the FFT. I will also highlight
applications of this Fast Slepian Transform in the context of
compressive sensing and processing of sampled multiband signals.
One approach for proving this conjecture is to prove that in every H-free graph G, there are two linear-size sets A and B such that either there are no edges between A and B, or every vertex in A is adjacent to every vertex in B. As is turns out, this is not true unless both H and its complement are trees. In the case when G contains neither H nor its complement as an induced subgraph, the conclusion above was conjectured to be true for all trees (Liebenau & Pilipczuk), and I will discuss a proof of this for a class of tree called "caterpillars".
I will also talk about results and open questions for some variants, including allowing one or both of A and B to have size n^c instead of linear size, and requiring the bipartite graph between A and B to have high or low density instead of being complete or empty. In particular, our results improve the bound on the size of the largest clique or stable that must be present in a graph with no induced five-cycle.
Joint work with Maria Chudnovsky, Jacob Fox, Anita Liebenau, Marcin Pilipczuk, Alex Scott, and Paul Seymour.
“sketches” of graphs that occupy much less space than the graph itself,
but where the shortest path distances of the graph can still be
approximately recovered from the sketch. For example, in the literature
on Spanners, we seek a sparse subgraph whose distance metric
approximates that of the original graph. In Emulator literature, we
relax the requirement that the approximating graph is a subgraph. Most
generally, in Distance Oracles, the sketch can be an arbitrary data
structure, so long as it can approximately answer queries about the
pairwise distance between nodes in the original graph.
Research on these objects typically focuses on optimizing the
worst-case tradeoff between the quality of the approximation and the
amount of space that the sketch occupies. In this talk, we will survey a
recent leap in understanding about this tradeoff, overturning the
conventional wisdom on the problem. Specifically, the tradeoff is not
smooth, but rather it follows a new discrete hierarchy in which the
quality of the approximation that can be obtained jumps considerably at
certain predictable size thresholds. The proof is graph-theoretic and
relies on building large families of graphs with large discrepancies in