Discrete Mathematics 2010-2022

We show that, for every $n$ and every surface $\Sigma$ (orientable or not), there is a graph $U$
embeddable on $\Sigma$ with at most $c n^2$ vertices that contains as minor every graph
embeddable on $\Sigma$ with $n$ vertices. The constant $c$ depends polynomially on the Euler
genus of $\Sigma$. This generalizes a well-known result for planar graphs due to Robertson, Seymour, and Thomas (``Quickly excluding a planar
graph'', J. Comb. Theory B, 1994) which states that the square grid on $4n^2$ vertices contains as minor every planar graph with $n$ vertices.

This is a joint work with Cyril Gavoille.

We prove that the multivariate independence polynomial of any hypergraph of maximum degree $\Delta$ has no zeroes on the complex polydisc of radius $\sim\frac{1}{e\Delta}$, centered at the origin. Up to logarithmic factors in $\Delta$, the result is optimal, even for graphs with all edge sizes greater than $2$. As a corollary, we get an FPTAS for approximating the independence polynomial in this region of the complex plane.
We furthermore prove the corresponding radius for the $k$-uniform linear hypertrees is $\Omega(\Delta^{-1/(k-1)})$, a significant discrepancy from the graph case.
Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali.


Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m313bdafcc0bb1e027dd43c65b06c1634}
\]

Abstract: Instead of solving the eigenvalue problem Tf=zf for a linear operator
T and eigenvalue z, we can use a multiplier B and instead solve the linear pencil problem BTf=zBf. This leads us to study the numerical range and essential numerical range of linear pencils. The essential numerical range is used to describe the set of spectral pollution when approximating the eigenvalue problem by projection and truncation methods. By taking intersection over various multipliers, we get sharp enclosures. We apply the results to various differential operators. This talk is based on joint work with Marco Marletta (Cardiff).