We show that for any graph on n vertices with minimum degree at least 0.827327 n admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on n vertices with minimum degree at least 0.82733 n admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than 0.9 n. This is joint work with Luke Postle.

The problem we consider is that of retrieving this order from the sampled graph; this may be referred to as graph seriation. We present a randomized graph seriation algorithm that, for a large class of probability functions, yields an ordering with error $O^{*}(\sqrt{n})$ with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption on the probability function, we obtain the vastly better rate $O^{*}(n^{\epsilon})$ for any $\epsilon > 0$.

This is joint work with Aaron Smith.

This is joint work with Stefan Bard.

The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group $\Gamma$, an oriented graph $G = (V,E)$ is called $\Gamma$-\emph{connected} if for every function $f : E \rightarrow \Gamma$ there is a flow $\phi : E \rightarrow \Gamma$ with $\phi(e) \neq f(e)$ for every $e \in E$ (note that taking $f = 0$ forces $\phi$ to be nowhere-zero). Jaeger et al.\ proved that every oriented 3-edge-connected graph is $\Gamma$-connected whenever $|\Gamma| \ge 6$. We prove that there are exponentially many solutions whenever $|\Gamma| \ge 8$. For the group $Z_6$ we prove that for every oriented 3-edge-connected $G = (V,E)$ with $\ell = |E| - |V| \ge 11$ and every $f: E \rightarrow Z_6$, there are at least $2^{ \sqrt{\ell} / \log \ell}$ flows $\phi$ with $\phi(e) \neq f(e)$ for every $e \in E$.

This is joint work with Matt DeVos, Rikke Langhede, and Robert Samal.

Based on joint work with Kevin Hendrey and David Wood.

In this talk, we show how the problem of existence of an Euler tour (family) in a hypergraph $H$ can be reduced to the analogous problem in some smaller hypergraphs that are derived from $H$ using an edge cut of $H$. In the process, new techniques of edge cut assignments and collapsed hypergraphs will be introduced. Moreover, we shall describe two divide-and-conquer-type algorithms based on these characterizations that construct an Euler tour (family) in a hypergraph if it exists.

This is joint work with Andrew Wagner.

The study of random embeddings was started by Stahl and White in the 1990's, the main questions were the distribution of genus (equivalently, of the number of faces). The case of a multigraph with a single vertex and with two vertices was completely understood. We extend this to multistars, multigraphs where all edges are incident with a single vertex. We use Stanley's result on enumerating permutations to precisely bound the expected number of faces of a multistar. We apply this to get an estimate on the expected number of faces of a general graph in terms of its degeneracy. We also report on work-in-progress about getting a logarithmic bound on the expected number of faces of a complete graph.

Joint work with Jesse Campion Loth, Kevin Halasz, Tomáš Masařík, and Bojan Mohar.