### Talks in 2016

#### Vortrag im Seminar für Kombinatorik und Optimierung

**Title:**Jigsaw Percolation on Random Graphs

**Speaker:**Oliver Cooley (TU Graz)

**Date:**Dienstag 13.12.2016, 14:15

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

**Abstract:**

Jigsaw percolation, introduced by Brummit, Chatterjee, Dey and Sivakoff, may be viewed as a measure of whether two graphs on the same vertex set are ``jointly connected'': Given two such graphs, we ``merge'' two vertices if they are connected in both graphs, and the new vertex inherits all of the neighbours of the old vertices in both graphs. We continue until no more vertices can be merged and say the process percolates} if it ends with a single vertex.

Bollob\'as and Riordan proved that if the two graphs are independent binomial random graphs $G(n,p_1)$ and $G(n,p_2)$, then there is a threshold for percolation based on the product $p_1p_2$ of the two edge probabilities. However, they only determined the location of this threshold up to a constant factor.

In this talk we will present work in progress towards finding the exact threshold. This is based on joint work with Tobias Kapetanopoulos, Tam\'as Makai and Kathrin Skubch.

#### Vortrag im Seminar für Kombinatorik und Optimierung

**Title:**Enumeration of combinatorial structures up to isomorphisms

**Speaker:**Philipp Sprüssel (TU Graz)

**Date:**Dienstag 6.12.2016, 14:15

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

**Abstract:**

This talk will be a gentle introduction to the field of enumerative combinatorics.

Generating functions are a standard tool in enumerative combinatorics. In order to count the objects in a given class of combinatorial structures, the numbers of objects of different sizes are represented in a formal power series. Constructive decompositions of the objects in the class correspond to certain functional operations for the power series. Tools for analysing such operations allow to determine the exact or asymptotic numbers of objects in the class. However, if one wants to count objects up to some type of isomorphism, this approach usually fails.

In this talk, we present a different formal representation of combinatorial classes that takes isomorphisms into account: cycle index sums. These formal sums represent not only the objects in a given class, but also the orbits of their automorphisms, which makes it possible to represent constructive decompositions by functional operations that depend on the orbit.

#### Strukturtheorie-Seminar

**Title:**Combinatorics of random matrix products

**Speaker:**Rafał Sałapata (Politechnika Wrocławska)

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

**Room:**AE02 (STEG006), Steyrergasse 30, EG

**Abstract:**

I will describe the limit moments of a random matrix of Wishart type $BB^*$, where $B$ is a product of (classically) independent rectangular random matrices, using combinatorics related to matricially free probability. Those moments will be expressed in terms of noncrossing partitions with even blocks related to certain words, and then using $R$-, $S$- and $T$-transforms well known in free probability we give an explicit formula for those moments, connecting them with the multivariate Fuss-Narayana polynomials. At the end I'll present some partial results without the assumption of independence of random matrices. The results are joint work with R. Lenczewski.

#### Vortrag im Seminar für Kombinatorik und Optimierung

**Title:**Boostrap percolation on the binomial random graph $G(n,p)$

**Speaker:**Tam\'as Makai (TU Graz)

**Date:**Dienstag 29.11.2016, 14:15

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

**Abstract:**

Bootstrap percolation on a graph, with infection threshold a positive integer $r$, is an infection process which starts out from a set of initially infected vertices and in each further step every vertex with at least $r$ infected neighbours becomes infected. The process stops once no further vertices can become infected.

We consider bootstrap percolation on the binomial random graph $G(n,p)$, when the set of initially infected vertices has size $a$, which was investigated by among others by Janson, \L uczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of infected vertices at the end of the process.

This is joint work with Mihyun Kang.

#### Zahlentheoretisches Kolloquium

**Title:**Heights, bad reduction and ranks of abelian varieties over number fields

**Speaker:**Prof. Dr. Fabien Mehdi Pazuki (University of Copenhagen)

**Date:**Montag, 28. 11. 2016, 10:30 Uhr

**Room:**Seminarraum Geometrie 1, Kopernikusgasse 24/4.Stock

**Abstract:**

Abstract: Let A be an abelian variety over a number field K. We are

interested in its group of K-rational points A(K), which is finitely

generated by the Mordell-Weil Theorem. We show how to provide an explicit

upper bound on the rank of A(K) in terms of the height of A and the

discriminant of K. The proof uses a new inequality between the height and

bad reduction primes, which is obtained by combining a jacobian argument,

a Bertini Theorem and the existence of unramified towers over certain

quadratic number fields.

#### Zahlentheoretisches Kolloquium

**Title:**Unexpected distribution phenomenon resulting from Cantor series expansions

**Speaker:**Dr. William Mance (Institute of Mathematics at the Polish Academy of Sciences)

**Date:**Dienstag, 22. 11. 2016, 10:00 Uhr

**Room:**HS M ''Chemie'', Kopernikusg. 24/II

**Abstract:**

Abstract: We explore in depth the number theoretic and statistical properties of certain sets of numbers arising from their Cantor series expansions. As a direct consequence of our main theorem we deduce numerous new results as well as strengthen known ones.

#### Vortrag im Seminar für Kombinatorik und Optimierung

**Title:**The Evolution of Random Graphs on Surfaces

**Speaker:**Chris Dowden (TU Graz)

**Date:**Dienstag 22.11.2016, 14:15

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

**Abstract:**

For integers $g,m\ge 0$ and $n>0$, let $S^g_{n,m}$ denote the graph taken uniformly at random from the set of all graphs on $\{1,2, \ldots , n\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S^g_{n,m}$, finding that there is often different asymptotic behaviour depending on the ratio $m/n$.

This is joint work with Mihyun Kang and Philipp Sprüssel.

#### Finanzmathematisches Kolloquium

**Title:**Stochastische Steuerung für Versicherungen: Alte und neue Ansätze und Probleme.

**Speaker:**Christian Hipp (Karlsruhe Institute of Technology)

**Date:**Freitag, 11. 11. 2016, 14:00 Uhr

**Room:**Seminarraum Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24/II

**Abstract:**

Abstract:

Stochastische Steuerung für Versicherungen ist mittlerweile ein lebendiges Teilgebiet der

Mathematik, es hat sich nach anfänglichen Versuchen, Methoden aus dem Finance zu adaptieren,

etwas eigenständiger weiterentwickelt. Dazu gehören Methoden zur Lösung von Integro-Differentialgleichungen,

von Nebenbedingungen, von Modifizierungen der Argumente für Viskositätslösungen und nicht-stationäre Ansätze

für Mischungsmodelle. Schwerpunkt liegt in der numerischen Umsetzung und der Interpretation der numerischen Resultate.

#### Vortrag im Seminar Kombinatorik und Optimierung

**Title:**Exact approaches and approximation results for knapsack problems with side constraints

**Speaker:**Rosario Scatamacchia (Politecnico di Torino)

**Date:**8.11.2016, 14:15

**Room:**Seminarraum AE06, Steyrergasse 30, Parterre

**Abstract:**

We propose exact solution approaches for two different

generalization of the 0-1 Knapsack Problem, that is the

0-1 Knapsack Problem with Setups and the 0-1 Collapsing

Knapsack Problem. In the first problem, the items belong

to disjoint families (or classes) and they can be picked

only if the corresponding family is activated. The

selection of a class involves setup costs and resource

consumptions thus affecting both the objective function

and the capacity constraint. In the 0-1 Collapsing

Knapsack Problem, the capacity of the knapsack is not a

scalar but a non-increasing function of the number of

items included, namely it is inversely related to the

number of items placed inside the knapsack. The solution

approaches we propose rely on an effective exploration of

a specific set of variables that leads to solve standard

knapsack problems and on dynamic programming. For the

Knapsack Problem with Setups, a series of approximation

results is also provided.

#### SFB-Seminar

**Title:**

**Speaker:**()

**Date:**Montag, 7.11.2016, 14 - 16 Uhr

**Room:**Seminarraum Geometrie 2, Kopernikusgasse 24/4.Stock

**Abstract:**

\vspace{1cm}

14:00: **Laia Amorós** (University of Luxembourg)

*From modular curves to Shimura curves: a p-adic
approach*

15:00:

**Tetiana Stepaniuk**(Lesya Ukrainka Eastern European National University)

*Approximative characteristics of*

classes of convolutions

classes of convolutions

#### FWF START Seminar

**Title:**Correlations of multiplicative functions and applications

**Speaker:**Oleksiy Klurman (University College London)

**Date:**3.11.2016, 11:00

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

**Abstract:**

We develop the asymptotic formulas for correlations

\[

\sum_{n\le x}f_1(P_1(n))f_2(P_2(n))\cdot \dots \cdot f_m(P_m(n))\] where $f_1,\dots,f_m$ are bounded ``pretentious'' multiplicative functions, under certain natural hypotheses. We then deduce several desirable consequences: first, we characterize all multiplicative functions $f:\mathbb{N}\to\{-1,+1\}$ with bounded partial sums. This answers a question of Erd\H{o}s from $1957$ in the form conjectured by Tao. Second, we show that if the average of the first divided difference of multiplicative function is zero, then either $f(n)=n^s$ for $\operatorname{Re}(s)<1$ or $|f(n)|$ is small on average. This settles an old conjecture of K\'atai. If time permits, we discuss multidimensional analog of the results above and its application to the study of Gowers norms of multiplicative functions. Finally, we apply these techniques to study sign patterns of $(f(n),f(n+1),f(n+2))$ and $(f(n),f(n+1),f(n+2),f(n+3))$ where $f:\mathbb{N}\to \{-1,1\}$ is a given multiplicative function.

#### Probevorlesung im Rahmen des Habilitationsverfahrens

**Title:**Martingale und eine Anwendung

**Speaker:**Dr. Stefan Thonhauser (TU Graz)

**Date:**28.11.2016, 15:00 Uhr

**Room:**A 306

**Abstract:**

Nach einer kurzen Wiederholung elementarer Eigenschaften von Martingalen betrachten wir das 'Optional Stopping Theorem' von Doob. Nach dessen Herleitung wollen wir dieses Resultat auf das Problem {\it Wie lange benötigt ein Affe in Erwartung um auf der Schreibmaschine ABRACADABRA zu tippen?} anwenden.

#### FoE-Kolloquium

**Title:**Infinite-Dimensional Phase Retrieval

**Speaker:**Philipp Grohs (Univ. Wien)

**Date:**Fr 21.10.2016, 14:00

**Room:**Hörsaal BE01, Steyrergasse

**Abstract:**

Phase retrieval refers to restoring a signal from intensity measurements

only and is important in several application areas ranging from X-ray crystallography and microscopy to audio processing and deep learning. Due to the substantial amount of missing information, phase retrieval problems are extremely challenging to solve numerically.

We shed some light on the origin of these difficulties and we propose a novel paradigm of weaker stability which actually achieves stable phase retrieval in several applications.

This is joint work with R. Al-Aifari (ETH Zurich), I. Daubechies (Duke University) and R. Yin (Duke University)

#### Conference in honor of the 60th birthday of Prof. Lajos Horváth

**Title:**From change point detection to functional data

**Speaker:**()

**Date:**October 14-15, 2016; Opening 9.50 a.m.

**Room:**Seminar room of Statistics (NT03098), Kopernikusgasse 24/III

**Abstract:**

#### Vortrag

**Title:**Stress testing using vine copulas

**Speaker:**Prof. Dr. Claudia Czado (TU München)

**Date:**Freitag, 14.10.2016, 10:30 Uhr

**Room:**SR Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24, 2.Stock

**Abstract:**

#### Vortrag im Seminar für Kombinatorik und Optimierung

**Title:**Supersaturation Problem for Colour-Critical Graphs

**Speaker:**Oleg Pikhurko (University of Warwick)

**Date:**Dienstag 11.10.2016, 14:00

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

**Abstract:**

Bitte geänderte Beginnzeit beachten (14:00 puenktlich) - Please note the changed starting time (14:00).

The Turan function ex$(n,F)$ of a graph $F$ is the maximum number of edges in an $F$-free graph with $n$ vertices. The results of Turan and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine the minimum number of copies of $F$ that a graph with n vertices and ex$(n,F)+q$ edges can have. In general, this problem seems to be very difficult and is wide open.

I will present joint results with Zed Yilma, where we concentrate on the case when $q=o(n^2)$ and $F$ is colour-critical (that is, the removal of some edge from $F$ decreases its chromatic number).

#### Advanced Topics in Discrete Mathematics

**Title:**The Strange Logic of Galton-Watson Trees

**Speaker:**Joel Spencer (Courant Institute, New York University)

**Date:**Freitag 7.10.2016, 10:30 (Coffee Break 10:00-10:30)

**Room:**Seminarraum 2 Geometrie, 4. Stock, Kopernikusgasse 24

**Abstract:**

The classic analysis of the probability that the Galton-Watson tree is infinite gives an equation with two solutions. What about other properties. For first order properties we show that the equation system has a unique solution. When conditioning on the tree being infinite the probabilities of first order properties are particularly nice. More generally we consider properties defined by tree automata. These are associated with Monadic Second Order Logic. There is then a natural equation system. Sometimes the system has rogue solutions, meaning solutions with no interpretation. This area combines structural combinatorics, probabilistic combinatorics and logic. (Joint work with Moumanti Podder.)

#### FWF START Seminar

**Title:**On lattices and their shortest vectors

**Speaker:**Florian Pausinger (Chair of Geometry and Visualization, TU München)

**Date:**4.10.2016, 14:15

**Room:**Seminarraum Analysis-Zahlentheorie

**Abstract:**

The hexagonal lattice gives the highest density circle packing among all lattices in the plane.

In this talk I first recall the basic notions about lattices in the plane, before I construct a sequence of lattices with integer bases that approximate the hexagonal lattice. The construction uses elementary number theory and is based on particular palindromic continued fraction expansions. As an application I obtain lattices modulo N with longest possible shortest distances.

**Title:**Discrete Geometry and Topology Colloquium

**Speaker:**()

**Date:**30.9.2016 (14 Uhr)

**Room:**Hörsaal BE01, Steyergasse 30

**Abstract:**

14:00 {\bf H. Edelsbrunner} (ISTA): {\bf Distances and divergences in

topological data analysis}.

Given a finite set in a metric space, the topological

analysis assesses its multi-scale connectivity quantified in terms

of a $1$-parameter family of homology groups. Going beyond metrics,

we show that the basic tools of topological data analysis also

apply when we measure dissimilarity with Bregman divergences.

A particularly interesting case is the relative entropy whose

infinitesimal version is known as the Fisher information metric.

It relates to the Euclidean metric on the sphere and, perhaps

surprisingly, the discrete Morse properties of random data

behaves the same as in Euclidean space.

{\bf Coffee Break}

15:30 {\bf Raman Sanyal} (Goethe-Univ.\ Frankfurt): {\bf The geometry of double posets}, In 1984 Stanley showed that partially ordered sets (posets)

can be studied from the perspective of geometry. His order- and chain

polytopes express combinatorial properties of posets as

geometric quantities, furnishing a number of deep results

in both combinatorics and geometry.

In 2011, Malvenuto and Reutenauer introduced double posets (finite

sets equipped with two partial order relations). This notion

underlies many constructions in algebraic combinatorics such as P-partitions,

Littlewood-Richardson rules, permutation statistics.

In this talk, I will explain how double posets can be studied from a geometric

point of view, highlighting connections to

centrally-symmetric polytopes (weak Hanner polytopes), combinatorial

optimization (anti-blocking polytopes), valuations on distributive lattices,

and generalized Hibi (semigroup) rings. This is joint work with T.\ Chappell

and T.\ Fried.

16:20 {\bf Wöden Kusner} (TU Graz): {\bf Critical packings, rigidity, and the radius function}.

There are a number of classical problems in geometric optimization that ask

for the ``best'' configuration of points with respect to some function. We are

interested in the relationships between various notions of criticality for

such functions on configuration spaces, in particular the injectivity or

packing radius. This is not a Morse function, but it has been observed to

be Morse-like, in that the topological notion of regularity can be defined

in an analogous way. Furthermore, there is a geometric interpretation from

rigidity theory that characterizes configurations as critical by the

existence of a strut measure.

#### Gastvortrag

**Title:**An Approximate Nerve Theorem

**Speaker:**Primoz Skraba (Jozef Stefan Institute, Ljubljana, Slovenija)

**Date:**22.9.2016, 10:00-11:00

**Room:**Seminarraum 2, Geometrie (Kopernikusgasse 24, 4.OG)

**Abstract:**

The Nerve Theorem is an implicit tool in most application of topological data analysis relating the topological type of a suitably nice space with a combinatorial description of the space, namely, the nerve of a cover of that space. It is required that it is a good cover, that each element and intersection is contractible or at least acyclic. In this talk, I will describe a weaker condition we call an epsilon-acyclic cover. It encodes the idea that if a cover is almost a good cover, the persistent homology of a filtration computed on the nerve is a good approximation of the persistent homology of a filtration on the underlying space. The main application of this result is to reduce the computational burden for computing persistence by allowing the use of coarser representations of the space (e.g. smaller simplicial complexes). I will also describe how to obtain explicit error bounds from local computations.

#### Gastvortrag

**Title:**The unexpected efficiency of persistent cohomology

**Speaker:**Ulrich Bauer (TU München)

**Date:**08.09.2016, 14:00-15:00

**Room:**HS D (Kopernikusgasse 24, 3.Stock)

**Abstract:**

I will discuss the efficient computation of the persistence barcode of a Vietoris--Rips filtration given a finite metric space. The implementation in the developed C++ code “Ripser” focuses on memory and time efficiency, where the code outperforms existing software by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency.

#### Gastvortrag

**Title:**Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching

**Speaker:**Sharath Raghvendra (Dept. of Computer Science, Virginia Tech, USA)

**Date:**05.09.2016, 10:00-11:00

**Room:**HS D (Kopernikusgasse 24, 3.Stock)

**Abstract:**

Motivated by real-time logistics, I will present a deterministic algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations. The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R. The algorithm that I present is based on a variant of the offline primal-dual method where the constraint for every edge is relaxed by a fixed multiplicative factor. Using the fact that the costs between locations satisfy triangle inequality, I will show that this deterministic algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models.

Bio: Dr. Sharath Raghvendra is an Assistant Professor in the Department of Computer Science at Virginia Tech. Before joining Virginia Tech, he spent two years as a postdoctoral scholar at Stanford University. Dr. Raghvendra received his Ph.D from Duke University in 2012 where he won the Best Doctoral Dissertation Award. He is also the recipient of NSF CRII Award in 2014. His research interests span design of algorithms for problems in computational geometry and graph theory.

#### Workshop

**Title:**Workshop on the occasion of the 50th birthday of Bettina Klinz

**Speaker:**G. Woeginger, A. Custic, G. Rote, V. Deineko, U. Pferschy ()

**Date:**10.8.2016, 10:00-17:00

**Room:**Seminarraum AE06, Steyrergasse 30, Parterre

**Abstract:**

-------------------------------------------------------------------------------------------------------

Program

======

10:00-10:30: Get together and coffee (Steyrergasse 30, 2nd floor)

10:30-10:40: Opening

10:40-11:25: Gerhard J. Woeginger (Eindhoven University of Technology)

LP relaxations for two scheduling problems

11:30-12:15: Ante Custic (Simon Fraser University)

The Bilinear Assignment Problem: Complexity, polynomially solvable special

cases and heuristics

12:15-14:15: Lunch break

14:15 -15:00: Günter Rote (FU Berlin)

Loopless Gray Code Enumeration and the Tower of Bucharest

15:05-15:50: Vladimir Deineko (Warwick Business School)

On solvable cases of the 2-period-balanced-TSP and benchmark test problems

15:50-16:05: Coffee break

16:05-16:50: Ulrich Pferschy (University of Graz)

The Quadratic TSP (without special cases...)

16:50-17:00: Closing

----------------------------------------------------------------------------------------------------

#### Zahlentheoretisches Kolloquium

**Title:**On terms of the $X$-coordinates of Pell equations which belong to some specific sequences

**Speaker:**Prof. Dr. Florian Luca (University of the Witwatersrand)

**Date:**Dienstag, 19. 7. 2016, ACHTUNG (geänderte Beginnzeit): 15:15 Uhr

**Room:**ACHTUNG (Ort hat sich geändert): HS D, Kopernikusgasse 24, 3.Stock

**Abstract:**

\begin{coauthors}

Coauthors: A. Dossavi-Yovo, B. Faye, B. Kafle and Alain Togb\'e

\end{coauthors}

Let $d\geq 2$ be an integer which is not a square. Let $(X_n,Y_n)_{n\ge 1}$ be the sequence of positive integer solutions $(X,Y)$ of the Pell equation $X^2-dY^2=c$, where $c\in \{\pm 1,\pm 4\}$. We then show that there is at most one

$n$ such that $X_n$ is a rep-digit in base $10$, with a few exceptions in $d$. The same result holds if we impose that $X_n$ is a rep-digit in any fixed integer base $b\ge 2$ or a member of the Fibonacci sequence. The proofs use linear forms in logarithms of algebraic numbers.