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

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

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.


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

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

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: 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: 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

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

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

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.


Speaker: ()
Date: Montag, 7.11.2016, 14 - 16 Uhr
Room: Seminarraum Geometrie 2, Kopernikusgasse 24/4.Stock


14:00: Laia Amorós (University of Luxembourg)
From modular curves to Shimura curves: a p-adic

15:00: Tetiana Stepaniuk (Lesya Ukrainka Eastern European National University)
Approximative characteristics of
classes of convolutions


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

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

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.


Title: Infinite-Dimensional Phase Retrieval
Speaker: Philipp Grohs (Univ. Wien)
Date: Fr 21.10.2016, 14:00
Room: Hörsaal BE01, Steyrergasse

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


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

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

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

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


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

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

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.


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)

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.


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)

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.


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)

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.


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



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

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

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.