### Talks in 2021

#### Combinatorics Seminar

**Title:**The jump of the clique chromatic number of random graphs

**Speaker:**Dieter Mitsche (Institut Camille Jordan, Lyon)

**Date:**Friday 17th December 14:15

**Room:**Online meeting (Webex)

**Abstract:**

The clique chromatic number of a graph is the smallest number of colours in a vertex colouring so that no maximal clique is monochromatic. In 2016 together with McDiarmid and Pralat we noted that around $p= n^{-\frac{1}{2}}$ the clique chromatic number of the random graph $G(n,p)$ changes by $n^{\Omega(1)}$ when we increase the edge-probability $p$ by $n^{o(1)}$, but left the details of this surprising phenomenon as an open problem.

In this paper we settle this problem, i.e., resolve the nature of this polynomial `jump' of the clique chromatic number of the random graph $G(n,p)$ around edge-probability $p = n^{-\frac{1}{2}}$. Our proof uses a mix of approximation and concentration arguments, which enables us (i) to go beyond Janson's inequality used in previous work and (ii) to determine the clique chromatic number of $G(n,p)$ up to logarithmic factors for any edge-probability p.

Joint work with Lyuben Lichev and Lutz Warnke.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Strukturtheorie-Seminar

**Title:**Infinite graphs from fractals

**Speaker:**Prof. Daniele D'Angeli (Univ. Cusano, Rom)

**Date:**Donnerstag, 16.12.2021, 14:00 s.t. (!!)

**Room:**Webex meeting

**Abstract:**

In this seminar I will discuss the construction and some

properties (isomorphism problem, horofunctions, etc) of infinite graphs

inspired by Sierpinski fractals.

Webex online meeting

https://tugraz.webex.com/tugraz-de/j.php?MTID=mf490139ca1aaae90c0cc6c2deb766164}

Meeting number: 2732 039 1497

Password: vW8tFF37Mrm

The meeting opens at 13:40, the 50min talk starts at 14:00

#### Doctoral Program Discrete Mathematics

**Title:**Discrete Mathematics Day

**Speaker:**()

**Date:**Friday 10th December 10:00-15:00

**Room:**Online meeting (Webex)

**Abstract:**

10:00 - 10:10 Opening

\vspace{.5cm}

10:10 - 11:00 Talk by Prof. Bojan Mohar (Simon Fraser University):

Graph Searching

\vspace{.5cm}

11:10 - 11:40 Talk by Dr. Christian Lindorfer (TU Graz, formerly DK-Project 01):

Pumping in multiple context-free languages

\vspace{.5cm}

11:40 - 13:30 Lunch Break :

Virtual joint lunch via gather.town from 12:00 at

https://gather.town/app/B6O2m96CQrju3Ku5/lunchroom

\vspace{.5cm}

13:30 - 14:00 Talk by Lucía Rossa (MU Leoben, DK-Project 08):

Rational self-affine tiles associated to standard and nonstandard digit systems

\vspace{.5cm}

14:10 - 15:00 Talk by Prof. Michael Krivelevich (Tel Aviv University):

Linearly sized induced odd subgraphs

\vspace{.5cm}

Talks will take place on Webex:

https://tugraz.webex.com/tugraz/j.php?MTID=ma5713d4058da3fba43db01d3e709e4ff

Abstracts can be found here:

https://www.math.tugraz.at/discrete/events/DK-Day-2021.pdf

#### Combinatorics Seminar

**Title:**Friendly bisections of random graphs

**Speaker:**Matthew Kwan (IST Austria)

**Date:**Friday 3rd December 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Resolving a conjecture of Füredi, we prove that almost every

$n$-vertex graph admits a partition of its vertex set into two parts of

equal size in which almost all vertices have more neighbours on their

own side than across. Our proof involves some new techniques for

studying processes driven by degree information in random graphs, which

may be of general interest.

This is joint work with Asaf Ferber, Bhargav Narayanan, Ashwin Sah and

Mehtaab Sawhney.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Zahlentheoretisches Kolloquium

**Title:**Pillai's problem in function fields

**Speaker:**Dr. Sebastian Heintze (TU Graz)

**Date:**03.12.2021, 14:00 Uhr

**Room:**Seminarraum Analysis-Zahlentheorie, Kopernikusgasse 24, 2.OG

**Abstract:**

We consider a variant of Pillai's problem over function fields in one variable over the field of complex numbers. For two given simple linear recurrence sequences satiasfying some weak conditions, we will prove that any nonzero element of the function field has only finitely many representations as difference of an element of the first and the second recurrence sequence, which can be effectively computed. Moreover, we give suitable conditions under which there are only finitely many, effectively computable, elements with more than one such representation.

#### Strukturtheorie-Seminar

**Title:**The structure of infinite primitive permutation groups

**Speaker:**Simon M. Smith (University of Lincoln, U.K.)

**Date:**Donnerstag, 2.12.2021, 11:00 s.t.

**Room:**Webex meeting

**Abstract:**

I will present a recent result which describes the structure of all subdegree-finite primitive permutation groups. This class of groups includes, for example, all automorphism groups of locally finite primitive graphs.

Webex meeting, meeting link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=mf5a44114a0937a3c1039cae265df3454}

Meeting number: 2730 920 3333

The meeting opens at 10:40, the 50min talk starts at 11:00

Password: bNDQ4FbVY44

#### Combinatorics Seminar

**Title:**The scaling limit of a critical random directed graph

**Speaker:**Christina Goldschmidt (University of Oxford)

**Date:**Friday 26th November 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We consider the random directed graph $D(n, p)$ with vertex set $\{1, 2, .\ldots , n\}$ in which each of the $n(n-1)$ possible directed edges is present independently with probability $p$. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at $p = 1/n$, with critical window $p = 1/n + \lambda n^{-4/3}$ for $\lambda \in \mathbb{R}$. We show that, within this critical window, the strongly connected components of $D(n, p)$, ranked in decreasing order of size and rescaled by $n^{-1/3}$, converge in distribution to a sequence of finite strongly connected directed multigraphs with edge lengths which are either $3$-regular or loops. This is joint work with Robin Stephenson (Sheffield).

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**Triangle factors and squares of Hamilton cycles in randomly perturbed graphs

**Speaker:**Julia Böttcher (London School of Economics)

**Date:**Friday 12th November 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We study the model of randomly perturbed dense graphs, which is the union of any $n$-vertex graph $G_b$ with minimum degree at least $bn$ for $b$ between $0$ and $1$ and the binomial random graph $G(n,p)$. In this talk, I will survey what is known about small and large subgraphs in this model and then concentrate on our new results concerning triangle factors (i.e. a spanning collection of vertex disjoint triangles) and squares of Hamilton cycles. I will also point out a number of interesting questions that remain open.

Joint work with Olaf Parczyk, Amedeo Sgueglia and Jozef Skokan.

#### Strukturtheorie-Seminar

**Title:**Universal planar graphs

**Speaker:**Florian Thomas (Lehner) (TU Graz)

**Date:**Donnerstag, 11.11.2021, 11:00 s.t.

**Room:**SR AE06, Steyrergasse 30, EG + Webex

**Abstract:**

Let $\mathcal{G}$ be a class of graphs. Call a graph $G \in \mathcal{G}$ subgraph-universal, minor-universal, or topological-minor-universal if it contains every graph in $\mathcal G$ as a subgraph, minor, or topological minor, respectively.

Answering a question posed by Ulam, Pach proved in 1981 that there is no subgraph-universal planar graph. In contrast to this result, Diestel and Kühn showed that a minor-universal planar graph exists and asked whether a universal planar graph exists for the topological minor relation.

We answer their question in two different ways: we show that the class of planar graphs does not contain a topological-minor-universal graph, but the class of locally finite planar graphs does.

The talk will by hybrid in presence / webex transmission.

For webex:

Meeting number: 2734 959 2527

Password: TWmWKjwu383

{https://tugraz.webex.com/tugraz-de/j.php?MTID=mfa18ddc81318b8ec0ce3587e95c9e287}

meeting to be opened at 10:45, the talk will start at 11:00

#### Combinatorics Seminar

**Title:**Quasirandom combinatorial structures and extremal combinatorics

**Speaker:**Daniel Kráľ (Masaryk University)

**Date:**Friday 5th November 14:15

**Room:**Seminarraum AE06, Steyrergasse 30, Erdgeschoss / Webex

**Abstract:**

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, uniform edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

In the first part of the talk, we will discuss quasirandom properties of several other combinatorial structures, in particular, tournaments, permutations and Latin squares, and present recent results obtained using analytic tools of the theory of combinatorial limits. In the second part of the talk, we will discuss several questions from extremal combinatorics related to quasirandom graphs and hypergraphs, in particular, the uniform Turán density of hypergraphs, which was introduced by Erdős and Sós in the early 1980s; we establish the existence of a hypergraph with uniform Turán density equal to 1/27, which answers a question of Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97], and determine the uniform Turán density of odd tight cycles.

The talk contains results obtained with different groups of collaborators, including Matija Bucić, Timothy F. N. Chan, Jacob W. Cooper, Frederik Garbe, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, David Munhá Correia, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

#### Mathematisches Kolloquium

**Title:**Stochastic differential equations with irregular coefficients: mind the gap! (Update)

**Speaker:**Michaela Szoelgyenyi (Universität Klagenfurt)

**Date:**05.11.2021, 14:00 Uhr

**Room:**Seminarraum Analysis-Zahlentheorie, Kopernikusgasse 24, 2.OG

**Abstract:**

Random phenomena often appear in dynamical systems that we aim to analyse and to control.

Mathematics serves to describe these random dynamical systems by stochastic differential equations (SDEs).

In many cases the coefficients of these SDEs lack regularity properties that are assumed in the classical literature on numerical methods for SDEs.

For example, when solving stochastic control problems by simulation one has to take into account that the control might depend on the controlled process in a discontinuous manner.

Motivated by this problem we study existence, uniqueness, and strong convergence rates of numerical methods for certain SDEs with non-globally Lipschitz coefficients.

#### Strukturtheorie-Seminar

**Title:**Quasiisometric embeddings of treebolic spaces

**Speaker:**Patrick Nairne (Oxford)

**Date:**Thursday, November 4, 2021, 11:00 on time

**Room:**webex virtual meeting

**Abstract:**

Treebolic spaces are examples of "horocyclic products", a fascinating class of metric spaces that encompasses Diestel-Lieder graphs and the 3-dimensional Lie group Sol. In particular, the solvable Baumslag-Solitar groups are quasiisometric to certain treebolic spaces. In this talk, we will characterise when you can quasiisometrically embed a treebolic space into another treebolic space. As a consequence, we will be able to characterise when two treebolic spaces are quasiisometric, thereby verifying a conjecture of Woess.

webex meeting, Thursday, 4 November 2021, 11:00 (Rome, Stockholm, Vienna)

Meeting number: 2731 084 7787

Password: 9WHexSX2UX3

{https://tugraz.webex.com/tugraz-de/j.php?MTID=mdfcf9b292d9aa2c2d97a55122584dd27}

meeting to be opened at 10:40, the talk will start at 11:00

#### Combinatorics Seminar

**Title:**Satisfiability of random linear systems

**Speaker:**Amin Coja-Oghlan (TU Dortmund)

**Date:**Friday 29nd October 14:15

**Room:**Online meeting (Webex)

**Abstract:**

For a sparse random matrix model with given numbers of non-zero entries in the rows and columns we identify a sufficient and very nearly necessary condition for the matrix having full row rank whp. The condition comes exclusively in terms of the degree distributions and holds for matrices with independent entries over finite fields. As an implication we obtain a full rank condition for random $0/1$ matrices over the rationals. Joint work with Max Hahn-Klimroth, Joon Lee, Noela Muller, Maurice Rolvien.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**Spanning $F$-cycles in random graphs

**Speaker:**Yury Person (TU Ilmenau)

**Date:**Friday 22nd October 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We extend a recent argument of Kahn, Narayanan and Park about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**Multitrees in random graphs

**Speaker:**Alan Frieze (Carnegie Mellon University)

**Date:**Friday 15th October 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Let $N=\binom{n}{2}$ and $s\geq 2$. Let

$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent

permutations of the edges $E(K_n)$ of the complete graph $K_n$. A

MultiTree is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$

induce spanning trees for $j=1,2,\ldots,s$. In this paper we study the

following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$

contains a multitree. We prove a hitting time result for $s=2$ and an

$O(n\log n)$ bound for $s\geq 3$.

Joint work with Wesley Pegden

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Strukturtheorie-Seminar

**Title:**Ratio limits and Martin boundary

**Speaker:**Wolfgang Woess (TU Graz)

**Date:**Donnerstag, 14.10.2021, 13:30

**Room:**Seminarraum AE06, Steyrergasse 30 Erdgeschoß

**Abstract:**

Consider an irreducible Markov chain which satisfies a ratio limit theorem, and let r be the spectral radius of the chain. We investigate the relation of the the

r-Martin boundary with the boundary induced by the r-harmonic kernel which appears

in the ratio limit. Special emphasis is on random walks on non-amenable groups,

specifically, free groups and hyperbolic groups.

This work was done in reply to questions posed by Adam Dor-On.

#### Mathematisches Kolloquium

**Title:**Problems in directional discrepancy (Update)

**Speaker:**Michelle Mastrianni MSc (University of Minnesota)

**Date:**12.10.2021, 14 Uhr

**Room:**Seminarraum Analysis-Zahlentheorie, Kopernikusgasse 24, 2.OG (+Webex)

**Abstract:**

The discrepancy of a point set in the unit cube provides a measure of

how well-distributed the point set is. However, precise behavior of

the discrepancy strongly depends on the properties of the underlying

collection of geometric test sets. In two dimensions, the discrepancy

with respect to axis-parallel rectangles and rectangles rotated in

arbitrary directions is well-understood. The increased complexity of

the latter collection leads to discrepancy bounds of polynomial order,

in contrast to logarithmic order in the axis-parallel case. In this

talk we will examine the "in between" and study what happens when we

restrict the allowed set of rotations to a smaller interval. We will

also briefly touch on some known bounds for even sparser classes of

allowed rotations such as infinite sequences.

Webex-Link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=meaeac4cf5cf5ef21b5ab6f1d77e108bc

Meeting-Kennnummer: 2733 614 5622

Passwort: b8Uq9JGwru8

#### Combinatorics Seminar

**Title:**Obstructions for graphs of linear rank-width at most $k$

**Speaker:**Sang-il Oum (IBS/KAIST)

**Date:**Friday 8th October 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Oum (2005) showed that graphs of bounded rank-width are well-quasi-ordered under taking pivot-minors, which implies that the list of excluded pivot-minors for the class of graphs of linear rank-width at most $k$ is finite. However, its proof is non-constructive and provides no algorithm to construct the list. We prove that every excluded pivot-minor for the class of graphs of linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices. This is joint work with Mamadou M. Kant\'{e}, Eun Jung Kim, and O-joung Kwon.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**Asymptotic Enumeration and Limit Laws for Multisets

**Speaker:**Konstantinos Panagiotou (LMU München)

**Date:**Friday 1st October 14:15

**Room:**Online meeting (Webex)

**Abstract:**

For a given combinatorial class $\mathcal{C}$ we study the class $\mathcal{G} = {\scriptstyle{Mset}}(\mathcal{C})$ satisfying the multiset construction, that is, any object in $\mathcal{G}$ is uniquely determined by a set of $\mathcal{C}$-objects paired with their multiplicities. For example, ${\scriptstyle{Mset}}(\mathbb{N})$ is (isomorphic to) the class of number partitions of positive integers, a prominent and well-studied case. The multiset construction appears naturally in the study of unlabeled objects, for example graphs or various structures related to number partitions. We perform a thorough analysis of the set $\mathcal{G}_{n,N}$ that contains all multisets in $\mathcal{G}$ having size $n$ and being comprised of $N$ objects from $\mathcal{C}$ when the counting sequence of $\mathcal{C}$ is governed by subexponential growth. In particular, we determine the asymptotic growth of $\mathcal{G}_{n,N}$ and we describe the typical limiting shape of these objects as $n$ and} $1 \ll N \le n$.

This is joint work with L. Ramzews.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**The longest induced path in a sparse random graph

**Speaker:**Stefan Glock (ETH Zürich)

**Date:**Friday 24th September 14:15

**Room:**Online meeting (Webex)

**Abstract:**

A long-standing problem in random graph theory has been to determine asymptotically the length of a longest induced path in sparse random graphs. Independent work of {\L}uczak and Suen from the 90s showed the existence of an induced path of roughly half the optimal size, which seems to be a barrier for certain natural approaches. Recently, in joint work with Dragani\'c and Krivelevich, we solved this problem. In the talk, I will discuss the history of the problem and give an overview of the proof.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Combinatorics Seminar

**Title:**Finding and using large subexpanders

**Speaker:**Hong Liu (University of Warwick)

**Date:**Friday 17th September 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We will discuss some recent work which utilises large expander subgraphs and some natural conditions that ensure the existence of such subgraphs. In particular, we shall introduce a notion of crux, which lower bounds the size of an expander subgraph in any given graph. We then show its connection with well-mixing vertices and embedding sparse graphs.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=ma70275cd258e7748417214793956c7bf }

\]

Meeting number: 188 980 7021

Password: ahMZ84fJYQ2

#### Geometrisches Kolloquium

**Title:**

**Speaker:**()

**Date:**19.8.2021, 14:00-16:15

**Room:**Hörsaal A, Kopernikusgasse 24/I

**Abstract:**

Am Donnerstag den 19.8.2021 sind alle Freunde der Geometrie herzlich zu einem Kolloquium im Hörsaal A der Neuen Technik eingeladen. Die Vortragenden sind drei geschätzte Kollegen, die mit dem Institut für Geometrie auf verschiedene Weise verbunden sind, und die einen Einblick in ihre Forschung geben werden.

Das Programm im Detail lautet wie folgt:

~

14:00 {\bf Helmut Pottmann} (KAUST)

Paneling architectural freeform surfaces

14:45 {\bf Florian Lehner} (TU Graz)

Folding polyominoes into cubes

15:30 {\bf Hans-Peter Schröcker} (Univ. Innsbruck)

Curves, Surfaces, and Motions

#### Zahlentheoretisches Kolloquium (Update)

**Title:**Sum-full sets are not zero-sum-free

**Speaker:**Prof. Peter Pal Pach (Universität Budapest)

**Date:**22.07.2021, 10:15 Uhr

**Room:**Webex Meeting

**Abstract:**

Let A be a finite, nonempty subset of an abelian group. We show that if every element of A is a sum of two other elements, then $A$ has a nonempty zero-sum subset. That is, a (finite, nonempty) sum-full subset of an abelian group is not zero-sum-free.

Joint work with Seva Lev and Janos Nagy.

The meeting takes place online, the WebEX link is:

https://tugraz.webex.com/tugraz/j.php?MTID=m99f6b3c137cc26b1b9d8d3577713cb2d

Meeting number: 121 534 3794

Password: iPdZunPN675

#### Rigorosum

**Title:**Polynomial functions on rings of dual numbers

**Speaker:**Amr Ali Abdulkader Al-Maktry, MSc (TU Graz)

**Date:**15.07.2021, 15:00

**Room:**Seminarraum Analysis-Zahlentheorie, Kopernikusgasse 24, 2.OG

**Abstract:**

Webex link:

https://tugraz.webex.com/tugraz/j.php?MTID=m58f8bc4908f41d88b861f86b2a62edbe

#### Master-Seminar

**Title:**Edwards and Montgomery Curves

**Speaker:**Thomas Hochreiter (TU Graz)

**Date:**14.7.2021, 14:15

**Room:**Seminarraum Analysis-Zahlentheorie (NT02008)

**Abstract:**

Based on elliptic curves in short Weierstrass form and their addition law, I am going to introduce elliptic curves in Edwards and Montgomery form. In the case of Montgomery curves, the main focus lies on the Montgomery ladder, a fast algorithm for scalar multiplication. The main advantage of Edwards curves is their complete addition law which will be discussed in detail.

#### Bachelor-Seminar

**Title:**Reguläre Sprachen auf Graphen

**Speaker:**Herwig Höhenberger (TU Graz)

**Date:**Donnerstag, 1.7.2021, 11:15

**Room:**Webex meeting

**Abstract:**

In diesem Seminarvortrag beschäftigen wir uns mit regulären Sprachen auf

verschiedenen Graphen. Nach einigen grundlegenden Definitionen zu regulären Sprachen und Cayley Graphen wird zunächst Regularität des Wortproblems einer

Gruppe charakterisiert. Danach werden Enden eines Graphen und Strips

eingeführt und mit deren Hilfe eine notwendige Bedingung für die Regularität der Sprache der überschneidungsfreien Wege bewiesen.

Webex Meeting

https://tugraz.webex.com/tugraz/j.php?MTID=m7efa725cb60c414219047d62db31e8b1}

Meeting ID: 121 725 0650

Passwort: XXwKig3Tw83

Meeting wird um 11:00 geöffnet, Vortrag beginnt um 11:15

#### Kolloquium Mathematische Physik

**Title:**Acoustic resonant frequencies in the asymptotic regime of high-contrast inclusions

**Speaker:**Andrea Mantile (Universite de Reims)

**Date:**29.6.2021, 16.00

**Room:**Webex

**Abstract:**

The presence in a homogeneous acoustic medium of a small scaled

inhomogeneity, enjoying a high contrast of both its mass density and

bulk modulus, amplifies the generated total fields.

This enhancement has tremendous applications in imaging, in the broad

sense, and material sciences, to cite a few. It has been observed and

quantified in the stationary regime where it is more pronounced when the

incident frequency is close to the {\em Minnaert frequency}

$\omega_M$ (a positive real value depending on the capacitance of the

perturbation). For this reason, in the literature,

this particular frequency is commonly referred to as a {\em resonance}.

Our results suggest that it should not be interpreted as such in the

common spectral sense and the purpose of my talk is

to enlighten the mechanism leading to the emergence of the scattering

enhancement.

The stationary scattering of classical waves may be interpreted as a

generalized eigenvalue problem for a frequency-dependent Schr\"odinger

operator and, unlike its quantum counterpart,

changing frequency implies a change of the scattering matrix. For the

acoustic scattering problem in the regime of a highly contrasted small

inclusion, such equivalent Hamiltonian, $h_{\varepsilon,\omega}$,

depends both on the frequency $\omega$ and on the scale parameter

$\varepsilon > 0$. After introducing $h_{\varepsilon,\omega}$,

I will show that the existence of a local maximum of the scattering

amplitude, occurring at the Minnaert frequency, is connected with its

discontinuous behavior in the limit as the size

of the inhomogeneity tends to zero. Precisely, $h_{\varepsilon,\omega}$

converges in the norm-resolvent sense to

the unperturbed Laplacian as $\varepsilon \to 0^+$ for all the

frequencies $\omega$ such that $\omega \neq \omega_M$, while for

$\omega = \omega_M$ it converges toward a point interaction Hamiltonian

(a point-like potentials localized

at the center of the small inhomogeneity), giving rise to a non-trivial

asymptotic scattering.

These results have been obtained in the framework of a joint project

with A.~Posilicano and M.~Sini.

Meeting Link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=m73c7ac4cb81c36fd9a641e07e0fbaa44

Meeting-Kennnummer: 121 693 0583

Passwort: e7jJ27qwvmc

#### Kolloquium Mathematische Physik

**Title:**Harmonic analysis methods in spectral theory

**Speaker:**Jean-Claude Cuenin (Loughborough University)

**Date:**29.6.2021, 14.00

**Room:**Webex

**Abstract:**

I will give a survey of how methods from harmonic analysis, particularly

those related to Fourier restriction theory, can be used in spectral and

scattering theory. Applications include eigenvalue estimates for

Schr\"odinger and Dirac operators with complex potentials.

https://tugraz.webex.com/tugraz-de/j.php?MTID=m0fa597cfd0a91101f1308d91cdb93454

Meeting-Kennnummer: 121 847 8003

Passwort: J3BnRDCXY73

#### Kolloquium Mathematische Physik

**Title:**Resolvent estimates for Schrödinger operators with complex potentials

**Speaker:**Petr Siegl (Queen's University Belfast)

**Date:**29.6.2021, 10.00

**Room:**Webex

**Abstract:**

We present an overview of results on the behavior of the resolvent norm of

Schr\"odinger operators with complex potentials. Our lower bounds employ a new

non-semi-classical pseudomode construction applicable for a wide class of

potentials exhibiting various behavior at infinity. Our upper bounds rely on

new sub-elliptic estimates on the boundary of the numerical range leading to

explicit asymptotic formulas for the resolvent norm. We explain the optimality

of our results, their relevance for problems in mathematical physics and

discuss several examples.

Meeting Link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=m2ee46593929ebab9b1a832b50c944301

Meeting-Kennnummer: 121 639 0115

Passwort: fMBni6ANh59

#### Kolloquium Mathematische Physik

**Title:**Variations of canonical measures: Riemann surfaces, graphs and hybrid curves

**Speaker:**Noema Nicolussi (Ecole polytechnique, Palaiseau)

**Date:**28.6.2021, 13.00

**Room:**Webex

**Abstract:**

There are many interesting parallels between the analysis and geometry of

Riemann surfaces and graphs. Both settings admit a canonical measure (the

Arakelov--Bergman and Zhang measures) and an associated canonical Green

function. In this talk, we focus on the following question: what is the limit of

the canonical measures along a sequence of degenerating Riemann surfaces?

It turns out that the classical Deligne-Mumford compactification of the moduli

space of Riemann surfaces cannot capture the limiting behavior. Combining

graph theory with tropical non-archimedean geometry, we obtain a full answer

and a new compactification in terms of hybrid curves. Understanding the limit

of the Green function leads to questions on a to-be-developed theory of

Laplacian differential operators on hybrid curves and layered metric graphs.

Based on joint work with Omid Amini (\'Ecole polytechnique).

Meeting Link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=m7bd0f8621ab8df3a24e180a29036946b

Meeting-Kennnummer: 121 126 1673

Passwort: P7Av3psUev8

#### Kolloquium Mathematische Physik

**Title:**Singular boundary conditions for Sturm–Liouville operators via perturbation theory

**Speaker:**Dale Frymark (Czech Academy of Sciences, Rez)

**Date:**28.6.2021, 10.00

**Room:**Webex

**Abstract:**

We show that all self-adjoint extensions of semi-bounded Sturm--Liouville

operators with general limit-circle endpoint(s) can be obtained via an

additive singular form bounded self-adjoint perturbation of rank equal to

the deficiency indices, say $d=1$ or $2$. This characterization generalizes

the well-known analog for semi-bounded Sturm--Liouville operators with

regular endpoints. Explicitly, every self-adjoint extension of the minimal

operator can be written as

\[

A_T = A_0 + B T B^*,

\]

where $A_0$ is a distinguished self-adjoint extension and $T$ is a

self-adjoint linear relation in $C^d$. The perturbation is singular in

the sense that it does not belong to the underlying Hilbert space but is

form bounded with respect to $A_0$, i.e. it belongs to $H_{-1}(A_0)$.

The construction of a boundary triple and compatible boundary pair for the

symmetric operator ensure that the perturbation is well-defined and

self-adjoint extensions are in a one-to-one correspondence with

self-adjoint relations $T$.

Meeting Link:

https://tugraz.webex.com/tugraz-de/j.php?MTID=mb3c9a9e742c92b7baf4a0eab64d672e0

Meeting-Kennnummer: 121 710 2860

Passwort: diCAwTT3M88

#### Colloquium Discrete Mathematics and Probability

**Title:**The geometry of Schatten p-classes

**Speaker:**Joscha Prochno, KFU Graz ()

**Date:**Fr 25.6.2021 13:00

**Room:**Videokonferenz

**Abstract:**

Since the Schatten $p$-classes $S_p$ share several structural properties with

$l_p$ spaces, they are often referred to as non-commutative $l_p$ spaces.

However, while the geometry of the latter is well understood, this is, in

many situations, not the case for the Schatten classes, and their structure

is considerably more involved.

But due to their role, for instance, in low-rank matrix recovery, there has

been increased interest in those spaces in recent years.

In this talk, we shall present a result on the asymptotic volume and volume

ratio of the unit balls in Schatten $p$-classes, settling a problem of

Saint Raymond (1984), who computed those quantities up to unspecified

constants. Using results from log-potential theory, we are able to compute

the precise asymptotics.

https://zoom.us/j/93350589439?pwd=L2t0MjU4MGRua2drZ1VmRW8wOWZZZz09}

Zoom Meeting ID: 933 5058 9439,

Passcode: 485031

#### Colloquium Discrete Mathematics and Probability

**Title:**Random growth processes: long-time behavior, non-equilibrium dynamics and competition

**Speaker:**Alexandre Stauffer (Univ. Bath / Univ. Roma Tre)

**Date:**Thu 24.6.2021 15:30

**Room:**Videokonferenz

**Abstract:**

Growth processes are random systems which grow over time spreading through

the vertices of a graph. There are several examples in the literature,

including spread of infection, deposition models, aggregation processes for

the formation of crystals and snowflakes, and electrodeposition.

In mathematics, growth processes are a major area of research. They include

processes with a bulky behavior (which are believed to produce a KPZ

scaling) and with dendritic formations (which are characterized by the

appearance of a delicate and beautiful geometry, with fractal-like

ramifications

that are yet very poorly understood). The main difficulty in analyzing such

processes come from their strong correlations arising from the

non-equilibrium dynamics.

In this talk I will review this area with special emphasis on the model of

multi-particle diffusion limited aggregation,

whose analysis has been widely open for almost 40 years, and a growth

process with competition which has been used as a tool to analyze such

challenging models.

https://zoom.us/j/97430416003?pwd=RWJoQmlHM0xSQzNkSU1PYkp5YVVZUT09}

Zoom Meeting ID: 974 3041 6003, Passcode: 303549

#### Colloquium Discrete Mathematics and Probability

**Title:**Hypergraph matchings with constraints

**Speaker:**Felix Joos (Univ. Heidelberg)

**Date:**Thu 24.6.2021, 13:00

**Room:**Videokonferenz

**Abstract:**

Numerous problems in combinatorics can be formulated as the

existence question of a perfect matching in a hypergraph. Not surprisingly,

this decision problem is NP-complete in general. For a very large class of

hypergraphs, Rödl and Pippenger-Spencer proved the existence of an almost

perfect matching, which is by now one of the most applied theorems in

extremal combinatorics. I discuss an extension of this theorem where the

matching satisfies a collection of additional properties. I also present

several applications.

https://tugraz.webex.com/tugraz/j.php?MTID=mc55a8fe86ecc398b498a691f71887eba}

Webex Meeting number: 121 892 8698,

Password: pbJmFYMN378

#### Colloquium Discrete Mathematics and Probability

**Title:**Interfaces in percolation theory

**Speaker:**Agelos Georgakopoulos (Univ. Warwick)

**Date:**Wed 23.6.2021, 15:30

**Room:**Videokonferenz

**Abstract:**

Answering a question of Kesten from 1981, C. Panagiotis and I proved that

for Bernoulli bond percolation on ${\mathbb Z}^d$, $d\ge 2$, the percolation density is an

analytic function of the parameter in the supercritical interval $(pc,1]$. The

proof involves tools from complex analysis, probability, and above all,

combinatorics. An important ingredient was a notion of interface we

introduced, which has already found further applications that I will

discuss

https://zoom.us/j/94847309678?pwd=V2E3V0lrTjRZYUE5dlpiNmVQcC8vZz09}

Zoom Meeting ID: 948 4730 9678,

Passcode: 225030

#### Colloquium Discrete Mathematics and Probability

**Title:**Combinatorial and probabilistic growth models

**Speaker:**Ecaterina Sava-Huss (Univ. Innsbruck)

**Date:**Di 22.6.2021, 13:00

**Room:**Videokonferenz

**Abstract:**

The focus of my talk is on cluster growth models based on

systems of interacting particles that move in a random or in a deterministic

fashion. I will start by introducing the basic tools for such models, which

are random walks and rotor walks. Then, with the help of such walks, I will

introduce the following aggregation models: internal DLA, rotor aggregation,

divisible sandpile and abelian sandpile. In all these models, one of the

main issues is to understand the limit shape behavior for a variety of

ground spaces. I will conclude my talk with ongoing and future work on iid

sandpiles and on the limit shape universality behavior.

https://tuwien.zoom.us/j/95699095299?pwd=aXZwcEtTeFRlOHNNdDZMZU1FeVh3dz09}

Zoom Meeting ID: 956 9909 5299, Password: BYT1Ev6a

#### Colloquium Discrete Mathematics and Probability

**Title:**Finite and Descriptive Combinatorics

**Speaker:**Oleg Pikhurko (Univ. Warwick)

**Date:**21.6.2021, 13:00

**Room:**Videokonferenz

**Abstract:**

We will focus on emerging connections between finite combinatorics and

areas that study analytic objects (such as measure theory, descriptive

set theory, measure-preserving group actions, etc). For example,

combinatorial methods and ideas have been successfully applied to find

constructive answers to foundational problems whose previously known

solutions crucially relied on the Axiom of Choice. In the other

direction, we will discuss some applications of analytic methods to

finite combinatorics.

https://zoom.us/j/96377616606?pwd=UVg4SngwbGQxQ2ZKY1dnRGZjQ2xsdz09}

(Zoom Meeting ID 963 7761 6606, Passcode: 225030)

#### Colloquium

**Title:**Discrete Mathematics and Probability

**Speaker:**()

**Date:**21.-25.6.2021

**Room:**Videokonferenz

**Abstract:**

Dies ist die Vorankuendigung von 6 Vortraegen (30 Minuten, gefolgt von einer Lehrprobe) zum Thema Diskrete Mathematik und Stochastik in der Woche 21.-25.6.

Mo 21.6 13:00 Oleg Pikhurko (Univ. Warwick)

Di 22.6. 13:00 Ecaterina Sava-Huss (Univ. Innsbruck)

Mi 23.6. 15:30 Agelos Georgakopoulos (Warwick Univ.)

Do 24.6. 13:00 Felix Joos (Univ. Heidelberg)

Do 24.6. 15:30 Alexandre Stauffer (Univ. Roma Tre / Univ. Bath)

Fr 25.6. 13:00 Joscha Prochno (KFU Graz)

#### Zahlentheoretisches Kolloquium

**Title:**Counting Quadratic Points on Surfaces

**Speaker:**Nick Rome (University of Michigan)

**Date:**Friday, 18.6.2021, 15:15

**Room:**online via Webex

**Abstract:**

We will discuss Manin's conjecture on rational points of bounded height on algebraic varieties. In particular, we will show how the recent counterexamples of Le Rudulier can be extended by counting quadratic points on certain del Pezzo surfaces.

Webex meeting data:

Meeting number: 121 827 9008

Password: pA58qDscPe9

https://tugraz.webex.com/tugraz/j.php?MTID=m295e4763fed4d65c8b8f3db204a7fadb

#### DK-colloquium

**Title:**The cost of automorphism breaking

**Speaker:**Prof. Wilfried Imrich (MU Leoben)

**Date:**Friday, June 18, 11:00; virtual coffee break at 10:30

**Room:**Webex meeting

**Abstract:**

This talk is a mathematical celebration of Wilfried Imrich's recent 80th birthday. He has had a very positive impact on our doctoral program (DK) `Discrete Mathematics', whence the talk is part of the running seminar of the DK.

Abstract: A coloring of the vertex set of a graph G is distinguishing if it

is preserved only by the identity automorphism. When two colors suffice,

then the vertex set V(G) of G can be partitioned into two sets, each of

which is preserved only by the identity automorphism. The minimum

cardinality of such a set is the 2-distinguishing cost r(G) of G. For

infinite graphs one can consider the minimal proportion of vertices of such

a set, the so-called 2-distinguishing density delta(G).

A particularly interesting class of graphs to investigate with respect to

r(G) and delta(G) are connected, vertex transitive, cubic graphs. They are

in the focus of the talk and lead to surprisingly nice results and numerous

open problems.

Virtual coffee break 10:30-11:00 in `gather town':

https://gather.town/app/xRPYyWll346RIYTR/DK-coffeebreak}

Password: coffee

The talk begins at 11:00 (CEST)

Webex-data for the talk:

https://tugraz.webex.com/tugraz/j.php?MTID=mfb7c5958c15df928aa27f1296d6264c3}

Meeting number: 174 286 6219

Password: hfJHu2sEV83

#### Strukturtheorie-Seminar

**Title:**The structure of vertex-transitive graphs, and applications to probability

**Speaker:**Dr. Matthew Tointon (University of Bristol)

**Date:**Thursday, 17 June 2021, 11:00 on time

**Room:**zoom-meeting

**Abstract:**

Trofimov famously proved that a vertex-transitive graph of

polynomial growth can be approximated in a certain precise sense by a

virtually nilpotent Cayley graph. In recent joint work, Romain Tessera and I

have proved a finitary, quantitative version of this statement. I will

describe the background to this result, talk a bit about its proof, and

describe some applications to random walks (also joint with Romain) and

percolation (joint with Tom Hutchcroft) on finite vertex-transitive graphs.

Zoom Meeting

https://bristol-ac-uk.zoom.us/j/97332812859?pwd=eFBSbDgzdm9JZk9CVG1iM2JFazF

YZz09}

Meeting ID: 973 3281 2859

Passcode: 652175

Meeting opens at 10:45, talk starts at 11:00 AM (Vienna time)

#### Zahlentheoretisches Kolloquium

**Title:**Universal quadratic forms, small norms and traces in families of number fields

**Speaker:**Magdaléna Tinková (Charles University, Prague)

**Date:**Friday, 11.6.2021, 15:15

**Room:**online via Webex

**Abstract:**

In this talk, we will discuss universal quadratic forms over number fields and their connection with additively indecomposable integers. In particular, we will focus on Shanks' family of the simplest cubic fields. This is joint work with Vítězslav Kala.

Webex meeting data:

Meeting number: 121 419 3115

Password: QakG6a4Vyw6

https://tugraz.webex.com/tugraz/j.php?MTID=m21d19e6abe2d4ed062ef1b6347c48b0b

#### Combinatorics Seminar

**Title:**Majority dynamics on sparse random graphs

**Speaker:**Joonkyung Lee (University College London)

**Date:**Friday 11th June 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Majority dynamics} on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erd\H{o}s--R\'enyi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$.

This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega\left(n^{-1/2}\right)$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $\lambda' n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda'>0$.

Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

#### Combinatorics Seminar

**Title:**The effect of VC-dimension on sunflowers

**Speaker:**Janos Pach (Alfréd Rényi Institute of Mathematics)

**Date:**Friday 4th June 14:15

**Room:**Online meeting (Webex)

**Abstract:**

According to the Erdos-Rado sunflower conjecture, for any integer $r>0$, there is a constant $c=c(r)>0$ such that any family of at least $c^k$ sets of size $k$ has $r$ members such that the intersection of every pair of them is the same. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension. We use a similar approach to attack other Ramsey-type questions. Joint work with Jacob Fox and Andrew Suk.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

#### Vortrag im Rahmen des Habilitationsverfahrens

**Title:**Das Banach-Tarski-Paradoxon

**Speaker:**Florian THOMAS (Institut für Diskrete Mathematik, TU Graz)

**Date:**Donnerstag, 10. Juni 2021, 9:00 bis 9:45

**Room:**https://tugraz.webex.com/meet/shoermann

**Abstract:**

Liebe Kolleginnen und Kollegen!

Am Donnerstag, dem 10. Juni 2021, findet der Probevortrag im Rahmen des Habilitationsverfahrens von Dr. Florian THOMAS zum Thema ``Das Banach-Tarski-Paradoxon'' statt.

Der Vortrag ist so gestaltet, dass er für Studierende des 5. und 6. Semesters geeignet ist.

#### Zahlentheoretisches Kolloquium

**Title:**POTENTIAL THEORY WITH MULTIVARIATE KERNELS

**Speaker:**Ryan Matzke (University of Minnesota)

**Date:**31.05.2021, 14 Uhr

**Room:**via Webex: https://tugraz.webex.com/meet/peter.grabner

**Abstract:**

In the past century, a great deal of study has been devoted to energy optimization problems. Given a compact metric space $\Omega$ and a kernel $K: \Omega^2 \rightarrow \mathbb{R} \cup \{\infty\}$, these problems involve finding points sets $\omega_N = \{ z_1, ..., z_N \}$ in $\Omega$ or Borel probability measures $\mu$ on $\Omega$ that minimize/maximize the discrete energy

$$ E_K( \omega_N) = \frac{1}{N^2} \sum_{j,k =1}^{N} K(z_j, z_k)$$

or the continuous energy

$$ I_K(\mu) = \int_{\Omega} \int_{\Omega} K(x,y) d\mu(x) d\mu(y),$$

respectively. Such optimization problems can have applications in signal processing, discrepancy theory, discretization of manifolds, discrete geometry, and models of physical phenomena, a classical example coming from the Thomson problem from 1904, which asks what configurations minimize the electrostatic potential energy of $N$ electrons on the sphere.

While a wealth of theory has been developed for classical energies, which model pairwise interactions between particles, of the above forms, there as been little to no systematic study of multivariate energies, defined by interatctions of triples, quadruples, or even higher numbers of particles, i.e. energies of the type

$$ E_K(\omega_N) = \frac{1}{N^n} \sum_{j_1, ..., j_n =1}^{N} K(z_{j_1}, ..., z_{j_{n}})$$

and

$$ I_K(\mu) = \int_{\Omega} \cdots \int_{\Omega} K(x _1, ..., x_n) d\mu(x_1) ... d\mu(x_n),$$

where $n \geq 3$ and $K: \Omega^n \rightarrow \mathbb{R} \cup \{\infty\}$. While less common than energies involving a two-input kernel, multivariate energies have appeared in various settings, including geometric measure theory, material science, and discrete geometry.

We discuss current progress in developing theory for multivariate energy optimization, such as semi-definite programming and the consequences of a generalization of positive definiteness. We will also discuss some applications, such as maximizing the squared expected area of a random triangle with vertices on the unit sphere.

The research in this presentation is joint work with Dmitriy Bilyk (University of Minnesota), Damir Ferizovi\'{c} (Graz University of Technology), Alexey Glazyrin (University of Texas Rio Grande Valley), Josiah Park (Texas A\&M University), and Oleksandr Vlasiuk (Florida State University).

(Die Abhaltung ist abhängig von der Coronalage - sofern möglich in Präsenz, ansonsten online via Webex)

#### Zahlentheoretisches Kolloquium

**Title:**Solving polynomial equations in many variables in primes

**Speaker:**Shuntaro Yamagishi (Universiteit Utrecht)

**Date:**Friday, 28.5.2021, 15:15

**Room:**online via Webex

**Abstract:**

Abstract: Solving polynomial equations in primes is a fundamental problem in number theory. For example, the twin prime conjecture can be phrased as the statement that the equation $x_1 - x_2 - 2 = 0$ has infinitely many solutions in primes. Let $F \in \mathbb{Z}[x_1, \ldots, x_n]$ be a degree $d$ homogeneous form. In 2014, Cook and Magyar proved the existence of prime solutions to the equation $F(x_1, \ldots, x_n) = 0$ under certain assumptions on $F$. In particular, their result requires the number of variables $n$ to be an exponential tower in $d$. I will talk about a result related to this work of Cook and Magyar improving on the number of variables required.

Webex meeting data:

Meeting number: 121 588 6334

Password: zHPC2W3MWY3

https://tugraz.webex.com/tugraz/j.php?MTID=m57168219dd765fdf05aad5386540e77e

#### Seminar für Kombinatorik und Optimierung

**Title:**Common subsequences between random words of very unequal length

**Speaker:**Boris Bukh (Carnegie Mellon University)

**Date:**Friday 28th May 14:30 (Irregular start time)

**Room:**Online meeting (Webex)

**Abstract:**

What is the longest common subsequence between a pair of random words? This problem is in general open. We describe the asymptotics for the case when one of the words is much longer than the other. We explain the connection to the problem of the longest nondecreasing subsequences in random words.

Joint work with Zichao Dong.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

#### Strukturtheorie-Seminar / Seminarium z Dyskretnej Analizy Harmonicznej

**Title:**Cyclic Boolean independence

**Speaker:**Franz Lehner (Technische Universität Graz)

**Date:**27.05.2021, 10:30 s.t.

**Room:**zoom video conference

**Abstract:**

The star product and comb product of finite graphs is simple enough to allow the explicit calculation spectra, Green's functions and various other parameters. The extension of these formulas to infinite dimensions leads to the abstract notions of cyclic Boolean and monotone independence. The talk reviews the basic aspects of cyclic Boolean independence which we found so far in joint work with O.Arizmendi and T.Hasebe.

zoom Meeting:

https://pwr-edu.zoom.us/j/98910283784?pwd=TU12bkRFcUd0d2VxWXlkUVlzcHQ5UT09}

Meeting ID: 989 1028 3784

Passcode: 912632

login at 10:15, the talk starts at 10:30

#### Seminar für Kombinatorik und Optimierung:

**Title:**Graph Pruning and its Application in Automatic Location Graph Construction

**Speaker:**Berhard Geiger and Christoph Schweimer (Know-Center Graz)

**Date:**25.5.2021, 9:00 (on time)

**Room:**online meeting via BigBlueButton

**Abstract:**

Abtract:

Given a graph with weighted edges, a common task is to find shortest paths

between vertices, i.e., paths with minimal weight. To facilitate such tasks, we

consider the problem of edge pruning: For any two vertices, the shortest paths

of the pruned graph have the same lengths as the shortest paths of the original

graph. In the first part of the talk, we briefly review existing approaches to

graph pruning and show that the computational complexity of the pruning task

reduces if the original graph satisfies certain conditions. The second part of

the talk is concerned with a concrete application of graph pruning, namely with

the construction of location graphs from map data. We show that our approach to

location graph construction ensures that the conditions for low computational

complexity are met and illustrate the performance of our algorithm at the hand

of several examples. Our work has practical relevance in areas such as logistics

optimisation and agent-based movement simulations.

After the talk there will be time for talk related questions and afterwards for an informal chat.

Meeting link (BigBlueButton)

\[

\text{https://cloud.tugraz.at/index.php/apps/bbb/b/SCdx29d4j8riLLk2}

\]

Meeting password (required): J6qofSS5

#### Seminar für Kombinatorik und Optimierung

**Title:**A sharp threshold for Ramsey's theorem

**Speaker:**Wojciech Samotij (Tel Aviv University)

**Date:**Friday 21st May 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Given graphs $G$ and $H$ and an integer $r \ge 2$, we write $G \to (H)_r$ if every $r$-colouring of the edges of $G$ contains contains a monochromatic copy of $H$. It follows from Ramsey's theorem that, when $n$ is sufficiently large, $G \to (H)_r$ is a nontrivial, monotone property of subgraphs $G$ of $K_n$. The celebrated work of Rödl and Ruci\'nski from the 1990s located the threshold for this property in the binomial random graph $G_{n,p}$ for all $H$ and $r$. We prove that this threshold is sharp when $H$ is a clique or a cycle, for every number of colours $r$; this extends earlier results of Friedgut, Rödl, Ruci\'nski, and Tetali and of Schacht and Schulenburg.

\noindent

This is joint work with Ehud Friedgut, Eden Kuperwasser, and Mathias Schacht.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

#### Strukturtheorie-Seminar

**Title:**Boundary behaviour of $\lambda$-polyharmonic functions on regular trees

**Speaker:**Wolfgang Woess (TU Graz)

**Date:**Thursday, 20 May 2021, 11:45 ON TIME

**Room:**Webex meeting

**Abstract:**

Abstract:

We study the boundary behaviour of $\lambda$-polyharmonic functions

for the simple random walk operator on a regular tree, where

$\lambda$ is complex and $|\lambda|> \rho$, the $\ell^2$-spectral

radius of the random walk. In particular, subject to normalisation

by spherical, resp. polyspherical functions, Dirichlet

and Riquier problems at infinity are solved and a non-tangential

Fatou theorem is proved. (Similar results for the hyperbolic

Laplacian on the unit disk are the object of current work.)

Joint publication with Ecaterina Sava-Huss (Innsbruck)

webex meeting, Thursday, 5 May 2021, 11:45 (Rome, Stockholm, Vienna)

Meeting number: 121 909 0134

Password: d73yU8FXhxx

https://tugraz.webex.com/tugraz/j.php?MTID=m16b9e7da9412c74e18da00735c141b2a}

meeting to be opened at 11:40, the talk will start at 11:45

#### Seminar für Kombinatorik und Optimierung

**Title:**Different angles of a defender-attacker-defender game in a graph

**Speaker:**Margarida Carvalho (University of Montreal)

**Date:**18.5.2021, 16:00 on time

**Room:**Webex virtual meeting

**Abstract:**

In integer programming games, players' feasible strategies are described by

lattice points inside polyhedra. This game representation is natural when

players' decisions have integrality restrictions. In this talk, we will start by

presenting practical examples of integer programming games. Then, we will focus on an integer programming game played between a defender and an attacker, the

Multilevel Critical Node problem. Besides a discussion on the problem

complexity, we will describe an exact cutting plane algorithm to determine the

game equilibrium and a greedy approach based on reinforcement learning to

approximate it.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=m48d957ba86eacd9738296225267e3312}

\]

Meeting number: 121 358 0969 Meeting password: tCs2sCK7qr3

#### Strukturtheorie-Seminar / Seminarium z Dyskretnej Analizy Harmonicznej

**Title:**Energy of graphs and vertices

**Speaker:**Octavio Arizmendi Echegaray (CIMAT Guanajuato and Saarbrücken)

**Date:**06.05.2021, 11:00 s.t.

**Room:**zoom videoconference

**Abstract:**

Energy of graphs, introduced in mathematics by Gutman in the 70's is a quite studied invariant of graphs. In (2018) with Juarez, we introduced a refinement called Energy of a Vertex. This allows to give better bounds and a local understanding for the energy of a graph. In this talk I will survey on the topic of Energy of Graphs and on recent results in relation with Energy of a Vertex, that I derived with various coauthors.

zoom Meeting:

https://pwr-edu.zoom.us/j/98910283784?pwd=TU12bkRFcUd0d2VxWXlkUVlzcHQ5UT09}

Meeting ID: 989 1028 3784

Passcode: 912632

login at 10:50, the talk starts at 11:00 (UTC+2).

#### Seminar für Kombinatorik und Optimierung

**Title:**Extremal problems for multigraphs

**Speaker:**Andrew Treglown (University of Birmingham)

**Date:**Friday 30th April 14:15

**Room:**Online meeting (Webex)

**Abstract:**

An $(n,s,q)$-graph is an $n$-vertex multigraph in which every $s$-set of vertices spans at most $q$ edges. Turan-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry posed the problem of determining the maximum of the product of the edge multiplicities in $(n,s,q)$-graphs. In this talk we will discuss recent progress on this problem, including a result that shows for infinitely many choices of $(s,q)$, the solution is transcendental. This answers a question of Alon. This is joint work with Nick Day and Victor Falgas-Ravry.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

#### Bachelor-Seminar

**Title:**Heaps of Pieces

**Speaker:**Martin Stoiber (TU Graz)

**Date:**Donnerstag, 29.4.2021, 11:00 püntklich (s.t.)

**Room:**Webex meeting

**Abstract:**

In diesem Seminarvortrag beschäftigen wir uns mit Viennots Theorie der Heaps of Pieces, aufbauend auf einen Artikel von C. Krattenthaler.

Zuerst werden einige grundlegende Definitionen wiederholt und anschließend wird das Konzept eines Heap of Pieces anhand eines Beispiels erklärt. Im Mittelpunkt dieses Vortrags steht der Satz über die Summe von Heaps of Pieces mit vorgegebenen maximal Pieces. Dieser wird zunächst theoretisch diskutiert und anhand einiger Beispiele demonstriert.

Webex meeting

meeting number: 121 451 4288

Password: t49Zpewcad3

https://tugraz.webex.com/tugraz/j.php?MTID=m3304b03a54f94da75787e8f833f901dc}

meeting wird um 10:45 geöffnet, der Vortrag wird um 11:00

beginnen.

#### Vortrag im Rahmen des Habilitationsverfahrens

**Title:**The Hahn-Banach Theorem

**Speaker:**Joshua Erde (Institut für Diskrete Mathematik, TU Graz)

**Date:**Fr. 23.4.2021, 11:00

**Room:**Video Conference (https://tugraz.webex.com, Meeting No. 174 286 6219, Password hfJHu2sEV83)

**Abstract:**

For a real normed vector space $V$, the

Hahn-Banach Theorem tells us that the dual space $V^*$ has a particularly

rich structure. We will prove the Hahn-Banach Theorem and discuss some of

its consequences.

#### Seminar für Kombinatorik und Optimierung

**Title:**Sharp thresholds and applications to extremal combinatorics

**Speaker:**Eoin Long (University of Birmingham)

**Date:**Friday 23rd April 14:15

**Room:**Online meeting (Webex)

**Abstract:**

Given $p \in [0,1]$, let $\mu _p$ denote the product measure on the cube $\{0,1\}^n$. It is well known that if ${\cal F} \subset \{0,1\}^n$ is a monotone family then the measure $\mu _p({\cal F})$ is monotonically increasing with $p$. The family has a sharp threshold at $p$ if a small increase in $p$ leads to a significant increase in $\mu _p ({\cal F})$.

The existence of sharp thresholds is of interest to a wide range of topics and has received considerable attention. When $p$ is bounded away from $0$ or $1$ the picture is quite well understood, but the case when $p$ is small is more challenging. In this talk I will discuss some recent results in this regime, which improve several previous bounds.

Our sharp threshold results also have significant applications in Extremal Combinatorics. Here we obtain new results on the Turán number of any bounded degree uniform hypergraph obtained as the expansion of a hypergraph of bounded uniformity. These results are asymptotically optimal and solve a number of open problems in the area.

Joint work with Peter Keevash, Noam Lifshitz and Dor Minzer.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

Password: e8pQ8ZBQN4B

#### Bachelor-Seminar

**Title:**Einführung der Abbildungsklassengruppe, Teil 2

**Speaker:**Matthias Müller (TU + KFU Graz)

**Date:**Donnerstag, 22.4.2021, 11:00 püntklich (s.t.)

**Room:**Webex meeting

**Abstract:**

This Bachelor seminar talk will be given in German !

Im zweiten Teil werden wir die Alexander-Methode formulieren und mittels Grundlagen über Dehn-Twists ein nicht triviales Beispiel der Abbildungsklassengruppe herleiten, Anwendungsbeispiele der Alexander-Methode hören und die Begriffe Simplex und Komplex besprechen. Den Abschluss bildet die Anwendung des Satzes von Dehn-Lickorish im Beweis zum Satz von Lickorish-Wallace in Hinblick auf dreidimensionale Mannigfaltigkeiten.

webex meeting

meeting number: 121 451 4288

Password: 3fKvgMKwE34

https://tugraz.webex.com/tugraz/j.php?MTID=m3b70821f24292b72d5c089c8326854a1}

meeting wird um 10:45 geöffnet, der Vortrag wird um 11:00

beginnen.

#### Bachelor-Seminar

**Title:**Einführung der Abbildungsklassengruppe

**Speaker:**Matthias Müller (TU + KFU Graz)

**Date:**Donnerstag, 15.04.2021, 11:00 püntklich (s.t.)

**Room:**Webex meeting

**Abstract:**

This Bachelor seminar talk will be given in German !

Abstract: In diesem Seminarvortrag beschäftigen wir uns mit dem Satz von

Dehn-Lickorish. Im Mittelpunkt steht die Einführung der

Abbildungs-klassengruppe und der Dehn-Twists. Dazu betrachten wir die

Elemente der Abbildungsklassengruppe am Besten, indem wir ihre Auswirkungen

auf Homotopieklassen einfacher, geschlossener Kurven studieren. Wir werden

sowohl fundamentale Beispiele der Abbildungs-klassengruppe als auch die

Alexander-Methode besprechen. Den Abschluss bildet die Anwendung des Satzes

von Dehn-Lickorish im Beweis zum Satz von Lickorish-Wallace in Hinblick auf

dreidimensionale Mannigfaltigkeiten und dient als Basis für viele Bereiche

der Mathematik: Die Nielsen-Thurston-Klassifikation teilt ihre Elemente in

periodische, reduzible und Pseudo-Anosov Abbildungsklassen ein.

Ein zweiter Vortrag (Fortsetzung) ist für die Folgewoche geplant, es wird eine nochmalige Einladung ergehen.

webex meeting

meeting number: 121 072 6735

Password: TPgavhDg335

https://tugraz.webex.com/tugraz/j.php?MTID=me31079b740c931cb97a5543456ef6239}

meeting wird um 10:30 geöffnet, der Vortrag wird um 11:00

beginnen.

Organisator/in: W. Woess

#### Habilitationsvortrag

**Title:**On hyperplane arrangements

**Speaker:**C. Ceballos Lopez (Institut für Geometrie, TU Graz)

**Date:**26.03.2021, 14:00 Uhr

**Room:**Webex: https://tugraz.webex.com/tugraz/j.php?MTID=mab843a1c06decf6a3798d343f34f25bb

**Abstract:**

Suppose you have an apple that you want to cut into as many pieces as possible, but you are allowed to use only ten slices. What is the maximum number of pieces you can obtain? How many of these pieces have no peel?

The purpose of this talk is to prove Zaslavsky's Theorem in the theory of hyperplane arrangements, which can used to answer these questions. If time permits, I would briefly discuss about hyperplane arrangements in complex vector spaces and their topological structure.

Webex-Passwort:

VTgx9VNPB75

#### Seminar für Kombinatorik und Optimierung

**Title:**Large independent sets from local considerations

**Speaker:**Benny Sudakov (ETH, Zürich)

**Date:**Friday 26th March 14:15

**Room:**Online meeting (Webex)

**Abstract:**

How well can global properties of a graph be inferred from observations that are purely local? This general question gives rise to numerous interesting problems. One such very natural question was raised independently by

Erdős-Hajnal and Linial-Rabinovich in the early 90's. How large must the independence number $\alpha (G)$ of a graph $G$ be whose every $m$ vertices

contain an independent set of size $r$? In this talk we discuss new methods to attack this problem which improve many previous results.

Joint work with M. Bucic

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

Password: e8pQ8ZBQN4B

#### Strukturtheorie-Seminar

**Title:**Confined random processes and Galois theory of difference equations

**Speaker:**Dr. Kilian Raschel (Univ. Tours)

**Date:**Thursday, 25 March 2021, 11:00 on time

**Room:**Webex meeting

**Abstract:**

Some models of random walks or Brownian motions in cones can be studied via functional equations that satisfy their Laplace transforms or generating functions. This approach applies to various situations, allowing to study first passage times, extinction probabilities, numbers of paths, stationary probabilities for reflected Brownian motion, etc.

It is rather easy to reformulate these functional equations in terms of q-difference equations, for example f(q*s) - f(s) = g(s), where f is the unknown function (typically the generating function), while g and q are known and depend on the model. Tools from the theory of difference equations are then perfectly adapted, in particular to characterize the algebraic nature of the solution, or even to compute it.

In this talk I will concentrate on applying this method to the enumeration of walks in the quarter plane, for which recent works by Dreyfus, Hardouin, Roques and Singer (arXiv:1702.04696 and arXiv:1710.02848) characterize the differential transcendence of the generating functions.

webex meeting, Thursday, 25 March 2021, 10:30 (Rome, Stockholm, Vienna)

Meeting number: 121 358 0191

Password: Rk33qX4uEZu

https://tugraz.webex.com/tugraz/j.php?MTID=m99b659bf5f6d78e9eb9eb8cbd3bb1fbe}

meeting to be opened at 10:30, the talk will start at 11:00

#### Seminar für Kombinatorik und Optimierung

**Title:**Flat Littlewood Polynomials Exist

**Speaker:**Rob Morris (IMPA)

**Date:**Friday 19th March 16:30

**Room:**Online meeting (Webex)

**Abstract:**

In a Littlewood polynomial, all coefficients are either $1$ or $-1$. Littlewood proved many beautiful theorems about these polynomials over his long life, and in his 1968 monograph he stated several influential conjectures about them. One of the most famous of these was inspired by a question of Erdős, who asked in 1957 whether there exist "flat" Littlewood polynomials of degree $n$, that is, with $|P(z)|$ of order $n^{1/2}$ for all (complex) $z$ with $|z| = 1$.

In this talk we will describe a proof that flat Littlewood polynomials of degree $n$ exist for all $n > 1$. The proof is entirely combinatorial, and uses probabilistic ideas from discrepancy theory.

Joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

Password: e8pQ8ZBQN4B

#### Strukturtheorie-Seminar

**Title:**The spectra of principal submatrices of rotationally invariant hermitian random matrices and the Markov--Krein correspondence

**Speaker:**Takahiro Hasebe (Hokkaido University)

**Date:**Thursday, 18. March 2021, 11:00 on time

**Room:**Webex meeting

**Abstract:**

We prove a concentration phenomenon for the empirical eigenvalue distribution (EED) of the principal submatrix of a random hermitian matrix whose distribution is invariant under unitary conjugacy; for example, this class includes GUE (Gaussian Unitary Ensemble) and Wishart matrices.

More precisely, if the EED of the whole matrix converges to some deterministic probability measure $\mu$, then its fluctuation from the EED of the principal submatrix, after a rescaling, concentrates at the Rayleigh measure (in general, a Schwartz distribution) determined from $\mu$ by the Markov--Krein correspondence.

For the proof, we use the moment method with Weingarten calculus.

At some stage of calculations, the proof requires a relation between the moments of the Rayleigh measure and the free cumulants of $\mu$.

This formula is more or less known, but we provide a different proof by observing a combinatorial structure of non-crossing partitions.

This is based on a joint work with Katsunori Fujie.

webex meeting, Thursday, 18 March 2021, 10:30 (Rome, Stockholm, Vienna)

Meeting number: 121 557 6754

Password: k5o9nFicjiQw4a

https://tugraz.webex.com/tugraz/j.php?MTID=ma0a08ae4a5c73c67e40ea84bdd03b069}

meeting to be opened at 10:30, the talk will start at 11:00

#### Algebra Kolloqium

**Title:**Split absolutely irreducible integer-valued polynomials over a DVR

**Speaker:**Sarah Nakato (Graz University of Technology)

**Date:**12.03.2021, 16 -16:55 Uhr

**Room:**https://tugraz.webex.com/tugraz/j.php?MTID=m4d59030a057d1ec54d69359ccfb74016

**Abstract:**

Let D be a domain with quotient field K. The ring of integer-valued polynomials on D, Int(D) = {f in K[X] | f(D) ⊆ D} in general is far from having unique factorization of elements into irreducibles. In this talk, we focus on the absolutely irreducible elements of Int(D) when D is a discrete valuation domain. Recall that an irreducible element of a commutative ring is called absolutely irreducible if none of its powers has more than one (essentially different) factorizations into irreducibles. We characterize the absolutely irreducible elements of Int(D) that split over D.

Meeting number: 121 582 6375

Password: IntRD

#### Algebra Kolloqium

**Title:**Rings of Integer-Valued Rational Functions

**Speaker:**Baian Liu (The Ohio State University)

**Date:**12.03.2021, 15 -15:55 Uhr

**Room:**https://tugraz.webex.com/tugraz/j.php?MTID=m4d59030a057d1ec54d69359ccfb74016

**Abstract:**

Let D be a domain and K its field of fractions. The ring of integer-valued polynomials, Int(D) = {f in K[X] | f(D) ⊆ D}, has been studied extensively from many angles. One generalization left largely untouched is to change from polynomials to rational functions: IntR(D) = {f in K(X) | f(D) is contained in D}. We know that Int(D) is not equal to D[X] only if there are enough residue fields of D that are finite. However, IntR(D) is not restricted in this way by infinite residue fields. For example, it is possible for a local domain D with an infinite residue field to have IntR(D) not equal to D[X]. This means that classifying IntR(D) by ideal-theoretic properties will look different from classifying Int(D). Loper and later Cahen, Chabert, and Frisch classified when Int(D) is Prüfer. In particular, Int(D) being Prüfer implies that D has Krull dimension of at most 1. For integer-valued rational functions, D can have Krull dimension greater than 1 and yet IntR(D) is still Prüfer. In this talk, I'll talk about properties of D and IntR(D) when IntR(D) is Prüfer.

Meeting number: 121 582 6375

Password: IntRD

#### Seminar für Kombinatorik und Optimierung

**Title:**Prague dimension of random graphs

**Speaker:**Lutz Warnke (Georgia Institute of Technology)

**Date:**Friday 12th March 14:15

**Room:**Online meeting (Webex)

**Abstract:**

The Prague dimension of graphs was introduced by Nešetřil, Pultr and Rödl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edge coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order $n/(\log n)$ for constant edge-probabilities.

The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size $O(\log n)$.

Based on joint work with He Guo and Kalen Patton, see https://arxiv.org/abs/2011.09459

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=me01f43109c693c884b459339d643d7d9}

\]

Meeting number: 121 128 5385

Password: e8pQ8ZBQN4B

#### Strukturtheorie-Seminar

**Title:**On the isomorphism problem for virtually free groups

**Speaker:**Dr. Armin Weiß (Institut für Formale Methoden der Informatik, Univ. Stuttgart)

**Date:**Thursday, 11. March 2021, 11:00 on time

**Room:**Webex meeting

**Abstract:**

The isomorphism problem for virtually free groups has been shown to be decidable by Krstic. Later the complexity has been improved to primitive recursive by Sénizergues in the case that the input is either given as two context free grammars for the word problems or as finite extensions of free groups. We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group G, compute a finite graph of groups with finite vertex groups and fundamental group G. Our algorithm is non-deterministic and runs in doubly exponential time. Using Krstic's algorithm for testing fundamental groups of graphs of groups for isomorphism, it follows that the isomorphism problem of context-free groups can be solved in doubly exponential space.

Moreover, if, instead of a grammar, a finite extension of a free group is given as input, the construction of the graph of groups is in NP and, consequently, the isomorphism problem in PSPACE. While the algorithm itself is rather simple and uses only standard tools from formal language theory, its proof of correctness is more geometric and it is based on the structure tree theory introduced by Dicks and Dunwoody. The talk will both describe the algorithm and explain these structure trees.

This talk is based on joint work with Volker Diekert and Géraud Sénizergues.

webex meeting, Thursday, 11 March 2021, 10:30 (Rome, Stockholm, Vienna)

Meeting number: 121 614 7730 ‚ Password: cpPXuc8xX35

https://tugraz.webex.com/tugraz/j.php?MTID=mfb27522952af189ef320ad424e4876d8

meeting to be opened at 10:30, the talk will start at 11:00

#### Seminar für Kombinatorik und Optimierung

**Title:**Knights and Liars on Graphs

**Speaker:**Paul Tabatabai (Polymer Competence Center Leoben )

**Date:**22.2.2021, 10:00 (on time)

**Room:**Webex virtual meeting

**Abstract:**

Abstract:

We discuss the Knights and Liars problem, which is the problem of maximizing the number of red vertices in a red-blue-coloring of the vertices on a square grid, such that for each red vertex, exactly half of its neighbors are red, and for each blue vertex, not} exactly half of its neighbors

are red. We discuss the generalization of the problem to arbitrary graphs and

provide an integer programming formulation, by which we give results for grid graphs, torus grid graphs, triangular grid graphs, and graphs corresponding to the transitive closure of the boolean lattice. We give a full combinatorial treatment for two-dimensional grid graphs whose shorter interval-size is less than seven. We further prove that the decision version of the generalized problem is NP-complete.

Joint work with Dieter P. Gruber

Meeting will be started at 9:30 a.m. for an informal chat. Talk starts at 10:00 a.m.

https://tugraz.webex.com/tugraz/j.php?MTID=m2394f3c4c58450f6e3bd1b6b700e3cb5

Meeting number (access code): 121 114 2286, password Uk4GvhrZ7p4

#### Seminar für Kombinatorik und Optimierung

**Title:**On the complexity of the bilevel minimum spanning tree problem

**Speaker:**Dorothee Henke (University of Dortmund)

**Date:**15.2.2021, 10:00 (on time)

**Room:**Webex virtual meeting

**Abstract:**

We consider the bilevel minimum spanning tree (BMST) problem where two decision

makers, the leader and the follower, each controlling a subset of the edges of a

graph, jointly choose a spanning tree. Each decision maker has their own

cost function on the edges and minimizes the sum of these costs over the chosen

spanning tree. Although BMST is a combinatorial bilevel optimization problem

that is easily defined, its computational complexity was an open question

stated recently by Shi et al. In this talk, we will answer this question by

showing that BMST is NP-hard in general

and that it remains hard even in special cases such as the one where the follower only controls a tree. Moreover, by relating BMST to vertex-disjoint

Steiner trees problems, we give some evidence that the problem might even remain

hard in case the follower controls only few edges.

We finally consider variants of BMST where one or both of the two decision makers have a bottleneck instead of a sum objective function. We settle the

complexity landscape of all combinations of sum or bottleneck objectives for the

leader and the follower, in the optimistic as well as the pessimistic setting.

(Joint work with Christoph Buchheim and Felix Hommelsheim)

Meeting will be started at 9:30 a.m. for an informal chat. Talk starts at 10:00 a.m.

https://tugraz.webex.com/tugraz/j.php?MTID=mb8dc363b285c3204089ce6b0d281f2ae

Meeting number (access code): 121 483 8939, password: 3gpMuWCm3q3

#### Seminar für Kombinatorik und Optimierung

**Title:**Robust Combinatorial Optimization with Locally Budgeted Uncertainty

**Speaker:**Stefan Lendl (University of Graz)

**Date:**8.2.2021, 10:00 (on time)

**Room:**Webex virtual meeting

**Abstract:**

Abstract:

Budgeted uncertainty sets have been established as a major influence on

uncertainty modeling for robust optimization problems. A drawback of such sets

is that the budget constraint only restricts the global amount of cost increase

that can be distributed by an adversary. Local restrictions, while being

important for many applications, cannot be modeled this way. We introduce new

variant of budgeted uncertainty sets, called locally budgeted uncertainty. In

this setting, the uncertain parameters become partitioned, such that a classic

budgeted uncertainty set applies to each partition, called region. In a

theoretical analysis, we show that the robust counterpart of such problems for

a constant number of regions remains solvable in polynomial time, if the

underlying nominal problem can be solved in polynomial time as well. If the

number of regions is unbounded, we show that the robust selection problem

remains solvable in polynomial time, while also providing hardness results for

other combinatorial problems. In computational experiments using both random

and real-world data, we show that using locally budgeted uncertainty sets can

have considerable advantages over classic budgeted uncertainty sets.

Joint work with Marc Goerigk.

Meeting will be started at 9:30 a.m. for an informal chat. Talk starts at 10:00 a.m.

https://tugraz.webex.com/tugraz/j.php?MTID=mb765ef4d86be77e471697fd82e2c87d7

Meeting number (access code): 121 851 5144, password: SYcE864R4mp

#### Postponed - Strukturtheorie-Seminar

**Title:**TALK POSTPONED Causal discovery for deterministic dynamical systems

**Speaker:**Prof. András Telcs (TU Budapest and Univ. Veszprém)

**Date:**Thursday, 4.Feb 2021, 11:00 on time

**Room:**Webex meeting

**Abstract:**

From philosophers of ancient times to modern economists, biologists and other researchers are engaged in revealing causal relations. The most challenging problem is inferring the type of the causal relationship: whether it is uni- or bi-directional or only apparent - implied by a hidden common cause only. Modern technology provides us tools to record data from complex systems such as the ecosystem of our planet or the human brain, but understanding their functioning needs detection and distinction of causal relationships of the system components without interventions. The talk presents a new method, which distinguishes and assigns probabilities to the presence of all the possible causal relations between two or more time series from dynamical systems. The new method is validated on synthetic data sets and applied to EEG (electroencephalographic) data recorded in epileptic patients. Given the universality of our method, it may find application in many fields of science.

webex meeting, Thursday, 4 February 2021, 10:30 (Rome, Stockholm, Vienna)

Meeting number: 121 501 6611 ‚ Password: QqxsEP3pN72

https://tugraz.webex.com/tugraz/j.php?MTID=m081516e9dce28bb660b408839fdfc678

meeting to be opened at 10:30, the talk will start at 11:00

#### Seminar für Kombinatorik und Optimierung

**Title:**The Erdos-Hajnal conjecture is true for $C_5$-free graphs

**Speaker:**Alex Scott (University of Oxford)

**Date:**Friday 29th January 14:15 (New meeting link)

**Room:**Online meeting (Webex)

**Abstract:**

It is well known that a graph on $n$ vertices need not have complete subgraphs or independent sets of size more than about $\log n$. But what if we consider graphs which do not contain some specific induced subgraph?

Erd\H{o}s and Hajnal conjectured in 1977 that for every graph $H$ there is a constant $c$ such that every graph on $n$ vertices without an induced copy of $H$ contains a clique or stable set of size $n^c$. The Erd\H{o}s-Hajnal conjecture is only known for $H$ belonging to a small family of graphs; and it is even open for some graphs on five vertices.

In this talk, we will show that the Erd\H{o}s-Hajnal conjecture is true when $H$ is a five-cycle, and discuss some related results. This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.

Meeting link:

\[

\text{https://tugraz.webex.com/tugraz/j.php?MTID=m91ec9c9750952c39a471f6bb21bf4e83}

\]

Meeting number: 121 709 2890

Password: JYc3B3dunG2

#### Zahlentheoretisches Kolloquium

**Title:**Distribution of primitive lattices and flags of lattices in Z^n

**Speaker:**Tal Horesh (IST Austria)

**Date:**Friday, 22.01.2021, 15:15

**Room:**online via Webex

**Abstract:**

Primitive lattice in $Z^n$ are a generalization of the concept of primitive vectors: a rank $d$ subgroup of $Z^n$ is called primitive if there is no other subgroup of the same rank that properly contains it. In two papers from 1998 and from 2015, Schmidt proved a counting statement for primitive lattices of any rank $1<d<n$, taking into account their shapes (similarity classes modulo rotation and rescaling, namely projections into $SO(d) \backslash SL_d(R)/ SL_d(Z))$, and directions (the subspaces that they span, namely projections into the Grasmannian $GR(d,n)$). We extend upon this counting statement, and also consider the shapes of the orthogonal complements of these lattices. Moreover, we introduce the concept of flags of primitive lattices, and extend this counting statement to them as well.

This is joint work with Yakov Karasik.

Meeting number: 121 139 9332

Password: fvNiUjUP332

Link:

https://tugraz.webex.com/tugraz/j.php?MTID=mb910f1333b42f13ca5aca85391713524

#### Seminar für Kombinatorik und Optimierung

**Title:**Thresholds

**Speaker:**Bhargav Narayanan (Rutgers University)

**Date:**Friday 22nd January 14:15

**Room:**Online meeting (Webex)

**Abstract:**

I'll discuss our recent proof of a conjecture of Talagrand, a fractional version of the ``expectation-threshold'' conjecture of Kahn and Kalai. As a consequence of this result, we resolve various (heretofore) difficult problems in probabilistic combinatorics and statistical physics. Time permitting, I’ll also outline how these methods can be used to determine the threshold of the square of the Hamilton cycle, a stubborn hitherto open problem in random graph theory.

Meeting link:

\[

\text{ https://tugraz.webex.com/tugraz/j.php?MTID=m1cd0904285a119237aa9a7ce985ad803}

\]

Meeting number:

137 149 1265

Password:

JYc3B3dunG2

#### Strukturtheorie-Seminar

**Title:**Geodesics and visual boundary of horospherical products

**Speaker:**Dr. Tom Ferragut (Univ. Montpellier)

**Date:**Thursday, 21.Jan. 2021, 11:00 on time

**Room:**Webex meeting

**Abstract:**

Horospherical products of two Gromov hyperbolic spaces unify the construction of metric spaces such as the Diestel-Leader graphs, the SOL geometry or the treebolic space. These examples, which are coming either from geometric group theory or from the study of solvable Lie groups, share similar rigidity properties.

In this talk we will first recall all the bases required to construct the horospherical products. Then we will study the large scale geometry of a family of them through a description of their geodesics and visual boundary.

webex meeting, Thursday, 21 Jan 2021, 10:30 (Rome, Stockholm, Vienna)

Meeting number: 121 802 9686 ‚ Password: u3Mpx5sJF2H

https://tugraz.webex.com/tugraz/j.php?MTID=macdcb248c84d8d6069425a0db76a2fc6

meeting to be opened at 10:30, the talk will start at 11:00

#### Seminar für Kombinatorik und Optimierung

**Title:**Divisible subdivisions

**Speaker:**Michael Krivelevich (Tel Aviv University)

**Date:**Friday 15th January 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We develop sufficient conditions for containment of graph subdivisions with subdivided edges of prescribed divisibility in terms of containment of graph minors. Concretely, we prove that for every graph H of maximum degree at most 3 and for every positive integer $q$ there is a finite $f=f(H,q)$ such that every minor of a complete graph $K_f$ contains a subdivision of $H$ in which every edge is replaced by a path whose length is divisible by $q$. Both the assumption of $\Delta(H) \leq 3$ and the requirement of zero residue modulo $q$ for path length are essential.

For the case of cycles we can do much better - we show that for $f=O(q \log q)$ every $K_f$-minor contains a cycle of length divisible by $q$. This result settles a recent problem of Friedman and Krivelevich about cycles in (weakly) expanding graphs.

A joint work with Noga Alon.

Meeting link:

\[

\text{ https://tugraz.webex.com/tugraz/j.php?MTID=m1cd0904285a119237aa9a7ce985ad803}

\]

Meeting number:

137 149 1265

Password:

JYc3B3dunG2

#### Seminar für Kombinatorik und Optimierung

**Title:**A Cantor-Bernstein-type theorem for spanning trees in infinite graphs

**Speaker:**Joshua Erde (TU Graz, Institut für Diskrete Mathematik)

**Date:**Friday 8th January 14:15

**Room:**Online meeting (Webex)

**Abstract:**

We consider the problem of when an infinite graph can be decomposed into an edge-disjoint union of $\lambda$ many spanning trees for a cardinal $\lambda$. Clearly it is necessary that the graph contains $\lambda$ many edge-disjoint spanning trees, and also that the graph can be covered with $\lambda$ many spanning trees. We show that these conditions are also sufficient.

For infinite $\lambda$ we use characterisations of when a graph contains $\lambda$ many edge-disjoint spanning trees or can be covered with $\lambda$ many spanning trees due to Erd\H{o}s and Hajnal, and Laviolette, and also give new simple proofs of these results. For finite $\lambda$ we prove a stronger statement using infinite matroids which can be seen as a generalisation of the Cantor-Bernstein theorem.

Joint work with Pascal Gollin, Attila Jo\'{o}, Paul Knappe and Max Pitz.

Meeting link:

\[

\text{ https://tugraz.webex.com/tugraz/j.php?MTID=m1cd0904285a119237aa9a7ce985ad803}

\]

Meeting number:

137 149 1265

Password:

JYc3B3dunG2