Noticias en español
Separating the edges of a graph by a linear number of paths
Abstract: A collection $\mathcal{P}$ of paths in a graph $G$ is called a \textit{strongly-separating path system} if, for any two edges $e$ and $f$ in $G$, there exist paths $P_e,P_f\in \mathcal{P}$ such that $e$ belongs to $P_e$ but not to $P_f$, and $f$ belongs to $P_f$ but not to $P_e$. If $\mathcal{P}$ contains a path that includes one edge but not the other, it is called a \textit{weakly-separating path system}. In 2014, Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan conjectured that every graph on $n$ vertices admits a weakly-separating path system of size $O(n)$....
Read MoreSpread measures on perfect matchings in regular pairs.
Abstract: The notion of spread distributions on copies of a given graph (or family of graphs) has played a crucial role in recent developments in probabilistic combinatorics, particularly in studying thresholds in random graphs. In this talk, I will show how to construct a spread distribution on perfect matching in regular pairs, which can be used together with the regularity lemma to find well-behaved embeddings of sparse graphs.
Read MoreHamiltonicity in pseudorandom graphs: absorbing paths.
Abstract: In this second talk, we will introduce the “extendability method” for embedding sparse structures in expander graphs and we will use it to construct efficient absorbers to solve the Hamiltonicity problem in pseudorandom graphs.
Read MoreHamiltonicity in pseudorandom graphs: Pósa rotation.
Abstract: In this series of talks, we will study different approaches to the Hamiltonicity problem in sparse pseudorandom graphs. In this first talk, we will review the celebrated “extension-rotation” technique pioneered by Pósa in the 70s and how to use it in pseudorandom graphs to find Hamilton cycles.
Read MoreAbstract: On 14/5 I gave a talk revolving around the fat minor conjecture. On 15/5 a paper appeared on Arxiv claiming to disprove it. I will report on this new development and I will attempt to offer a comprehensive view of the new questions that it raises, such as “Is this for real?” and “What now?”.
Read More