Discrete Mathematics 2010-2022

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

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

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

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

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.

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

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

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.

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

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 }
\]

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.

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

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

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

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

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.

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

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

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

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

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

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

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

Webex link:

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

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.

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

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

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

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

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

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

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

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

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

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

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

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)

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)

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

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

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)

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

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

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

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.

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)

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

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

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

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

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

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

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

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).

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

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.

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.

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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