Noticias en español
Powers of Hamilton cycles in directed and oriented graphs.
Abstract: The P\’osa–Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Koml\’os, S\’ark\”ozy and Szemer\’edi proved the conjecture for sufficiently large graphs. We focus on the analogous problem for digraphs and for oriented graphs. For digraphs, we asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more...
Read MoreSeparating the edges of a graph with linearly many subdivisions of K_4.
Abstract: Let G be a graph. As we recall from Ana’s talk, a set S of subgraphs of G is (strongly) separating if for every ordered pair of edges (e,f) in E(G)^2 there exists a subgraph H in S that contains e but not f. Although we traditionally view S as a set of paths, other kinds of separating sets have also been considered. Recently, Botler and Naia proved that every graph can be separated by a set S of subdivisions of K_4 (and lone edges, which are necessary for covering bridges), such that the size of S is a linear function of |V(G)|. This mirrors the corresponding theorem about...
Read MoreDrawing Planar Graphs Badly.
Abstract: We study how far one can deviate from optimal behavior when drawing a planar graph on a plane. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a \textit{plane-saturated subgraph} if adding any edge (possibly with a new vertex) to $H$ would either violate planarity or make the resulting graph no longer a subgraph of $G$. For a planar graph $G$, we define the \textit{plane-saturation ratio}, $\psr(G)$, as the minimum value of $\frac{e(H)}{e(G)}$ for a plane-saturated subgraph $H\subseteq G$ and investigate how small $\psr(G)$ can be. While there exist planar...
Read MoreSeparating 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 More