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

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.

Gastvortrag

Title: On Soft Foundations for Geometric Computation
Speaker: Chee Yap (New York University (NYU))
Date: 19.07.2016, 14:00-15:00
Room: HS D (Kopernikusgasse 24, 3.Stock)
Abstract:

For over two decades, Exact Geometric Computation (EGC) has provided a paradigm in Computational Geometry for the correct implementation of geometric algorithms. It is the most successful approach for addressing numerical nonrobustness, leading to successful libraries and practical algorithms
in many areas. We review some pressing reasons to extend this paradigm:

* EGC algorithms may not be Turing computable (e.g., transcendental functions)

* EGC may be too inefficient (e.g., shortest path problems)

* EGC entails numerous/difficult algebraic analysis (e.g., Voronoi diagram of polyhedra)

* Exact computation is unnecessary/inappropriate (e.g., robot motion planning)

This talk describes a research program to develop ``soft'' (i.e., purely numerical) approaches for addressing the above issues. We illustrate these ideas by looking at recent work in several areas:

* root isolation and clustering (ISSAC'09,'11,'12,'16, SNC'11, CiE'13)

* isotopic approximation of curves and surfaces (SoCG'09,'12, SPM'12, ICMS'14)

* Voronoi diagrams (ISVD'13, SGP'16)

* robot motion planning (SoCG'13, WAFR'14, FAW'15)

Some common themes emerge from the above list: we replace the exact algebraic model of computation (Real RAM or BSS Model) by a model based on numerical interval approximations. The main algorithmic paradigms are subdivision and iteration. We introduce an input resolution parameter (epsilon), but it must
be used in a novel ``soft way''. Soft versions of classical (``hard'')
geometric predicates must be developed.

What are the consequences of such a computational paradigm ?

* scope of computational geometry would be vastly broadened

* some unsolvable problems in the Real RAM model becomes possible

* soft algorithms are not only implementable but can be practical

One challenge is to revisit classical problems of computational
geometry from this new view point. Another challenge is to
produce complexity analysis of such algorithms.

Strukturtheorie-Seminar

Title: Infinite words: trees, fractals, and wild spaces
Speaker: Dr. Wolfram Hojka (TU Wien)
Date: Friday, 8. July, 11:15
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

For an iterated function system, the points of the attractor can be encoded by infinite words on a finite alphabet. Typically, the associated Cayley graph forms a tree; but when it does not, topological properties of the attractor can be deduced from the graph itself by using methods from geometric group theory. In particular, if the graph has only one end, the attractor is connected.

Groups of infinite words also appear in the algebraic description of wild topological spaces, such as the Hawaiian earring and the harmonic archipelago. Using a variety of tools (combinatorial dynamics, infinite systems of equations, classical abelian group theory), we highlight some surprising aspects of their homology and their fundamental groups.

Strukturtheorie-Seminar

Title: Amenability, Ore condition and determinants over group algebras
Speaker: Dr. Dawid Kielak (Universität Bielefeld)
Date: Friday, 8. July, 10:00 s.t. (!!)
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

We will discuss the Ore condition for group rings in the context of the open problem of embedding group algebras of torsion free groups into skew-fields. We will report on the recent result joint with L. Bartholdi which confirms the conjectured equivalence of Ore condition for group algebras with amenability of the underlying group.

We will then proceed to highlight a connection between the Ore condition and
the free calculus of Fox, and see how that in turn relates to 3-manifold invariants and $L^2$ homology via deteminants of matrices over a group algebra. These last results were obtained jointly with F. Funke.

Structure theory and stochastics seminar

Title: Cluster growth models on fractal graphs
Speaker: Dr. Ecaterina Sava-Huss (Technische Universität Graz)
Date: Thursday, July 07, 2016; 11:00
Room: SR A306, Steyrergasse 30/III
Abstract:

IDLA is a random growth model on a graph, in which particles move randomly around until finding an empty site where they stop and stick to an existing initial cluster. One of the main questions here is to understand the shape of the (random) growing cluster of occupied sites, when we start a large number of particles at the origin (or any fixed vertex) of our graph. I will first describe briefly the model, the connection with other models, and the state of the art. Then I will state some new results about the shape of IDLA on Sierpinski gasket graphs.
This is based on a joint work (in progress) with Joe Chen, Wilfried Huss and Alexander Teplyaev.

Structure theory and stochastics seminar

Title: Hydrodynamic limit of particle systems on the Sierpinski gasket
Speaker: Dr. Joe Chen (University of Connecticut)
Date: Tuesday, 05.07.2016, 10:15
Room: SR A306, Steyrergasse 30/III
Abstract:

The construction of a Brownian motion on a self-similar fractal was intensely studied in the 80s and 90s. For many fractals, such as the Sierpinski gasket, the approach is to consider (single-particle) random walks on the graphs approximating the fractal, rescale space and time, and then prove that a scaling limit exist.

Now consider, on a fractal graph, multiple random walkers which interact with each other according to some local rules. Fix an initial density of random walkers at time 0, and evolve the system in time. Can one prove a scaling limit of the time-evolving particle densities along successive graph approximations of the fractal? And if so, what is the limit object?

We answer this question positively in the setting of the (weakly asymmetric) exclusion process on the Sierpinski gasket. In this case, the scaling is the same as the diffusive scaling for single-particle random walks, and the limit of the particle densities evolves according to a (nonlinear) heat equation (a law of large numbers result). We can also characterize the fluctuations about the mean of the density (a large deviations result). In this talk, I will describe what these results mean precisely, and mention one or two key technical tools used to prove them.

Joint work with Alexander Teplyaev.

FESTVORTRAG

Title: The injective hull of a $T_0$-quasi-metric space
Speaker: Prof. Dr. Hans-Peter Künzi (University of Cape Town)
Date: Freitag, 1. Juli 2016, 14:00 Uhr
Room: Seminarraum Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24/II, TU Graz
Abstract:

Title: AUSTRIAN STOCHASTIC DAYS
Speaker: invited speakers: Mathias Beiglböck (Vienna), Rudolf Grübel (Hannover) ()
Date: Thursday, 30. June 2016 + Friday, 1. July 2016
Room: Seminar room of the Statistics Institute, Kopernikusgasse 24, 3rd floor
Abstract:

The program starts on Thursday, 30. June at 10:00 (coffee break), followed by the talk by M. Beiglböck (10:30), and continues with contributed talks.

On Friday, 1. July, the program starts at 9:00 with contributed talks; the invited talk by R. Grübel is at 10:30 and is also part of the ``Advanced Topics'' seminar of the DK ``Discrete Mathematics''.

For details, see

www.math.tugraz.at/mathc/stochdays/


Vortrag im Seminar für Kombinatorik und Optimierung

Title: Law of large numbers for the largest component of random graphs on the hyperbolic plane
Speaker: Nikolaos Fountoulakis (University of Birmingham)
Date: Dienstag 28.6.2016, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

In this talk, we consider a recent model which was developed by Krioukov et al. of random geometric graphs on the hyperbolic plane. This may be also viewed as the geometrisation of the well-known Chung-Lu model of inhomogeneous random graphs. We show that the size of the largest connected component undergoes a phase transition and a giant component emerges as soon as the curvature of the underlying hyperbolic plane crosses a certain value. We also show that the fraction of vertices that are contained there converges in probability to a certain constant, which is related to a continuum percolation model on the upper-half plane.

This is joint work with Tobias Müller (Utrecht University).

Title: Differential Geometry Minicolloquium
Speaker: (TU Wien, TU Graz)
Date: Friday 24.6.2016, 14:00
Room: Seminarraum 2, Kopernikusgasse 24/4
Abstract:

~[2cm]

14:00 Gudrun Szewieczek (TU Wien): About special triply orthogonal systems

14:30 Wolfgang Carl (TU Graz): Semidiscrete cmc surfaces

15:00 Coffee Break

15:30 Andreas Fuchs (TU Wien): Transformations of isothermic channel surfaces

16:00 Volker Branding (TU Wien): Prescribing Curvature and Torsion on Surfaces

Vortrag im Seminar Kombinatorik und Optimierung

Title: Bottleneck and linear assignment problems in geometric graphs
Speaker: Arnur Nigmetov (Institut für Geometrie, TU Graz)
Date: 21.6.2016, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Parterre
Abstract:

The talk will be about using geometric data structures to solve the
bottleneck and linear assignment problems in geometric graphs. The motivation is
computational topology, where these problems appear for persistence diagrams, which are subsets of the plane, so we are going to deal with bipartite graphs embedded in $\mathbb{R}^2$ with edge cost being some power of the distance between the vertices.  The main underlying structure in both problems will be k-d tree (with some modifications for the linear assignment problem).

Festkolloquium

Title: Reminder: Festkolloquium anlässlich des 75. Geburtstages von emer. o. Univ. Prof. Dr. Wilfried Imrich
Speaker: Prof. Peter Kirschenhofer (Laudatio), Prof. Wolfgang Woess, Dr. Florian Lehner, Prof. Sandi Klavžar, Prof. Rafał Kalinowski ()
Date: Freitag, 17. Juni 2016, 10:00 bis 16:00
Room: Hörsaal BE01, TU Graz, Steyrergasse 30, Erdgeschoß
Abstract:

10:00 - 10:30
Kaffeepause im Foyer

10:30 - 10:40
Prof. Peter Kirschenhofer (Leoben)
Laudatio

10:45 - 11:30
Prof. Wolfgang Woess (Graz)
Ultrametric spaces, trees, and random walks

11:45 - 12:30
Dr. Florian Lehner (Hamburg)
Automorphism groups of one-ended graphs

Mittagspause

14:15 - 15:00
Prof. Sandi Klavžar (Ljubljana)
Extending Wiener index to arbitrary partitions

15:15 - 16:00
Prof. Rafał Kalinowski (Kraków)
From chaos on trees to symmetry breaking

Strukturtheorie-Seminar

Title: Graphs and topological groups
Speaker: Rögnvaldur G. Möller (University of Iceland, Rykjavik)
Date: Thursday, 16. June 2016, 11:00 s.t.
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

A brief overview will be given of how graphs can be used in the theory of topological groups and how results about topological groups can be applied in the study of automorphism groups of graphs. In particular, the connections between the minimal valency of a so called Abels-Cayley graph for a totally disconnected locally compact group and the structure of the groups is explained.

Vortrag im Seminar Kombinatorik und Optimierung

Title: Lower bounds for online bin packing problems (survey)
Speaker: Gabor Galambos (University of Szeged, Hungary)
Date: 14.6. 2016, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Parterre
Abstract:

The classical bin packing problem requires to pack n elements with sizes $a_i$, $0\le a_i\le 1$ for $i=1,....,n$, into a minimum number of unit capacity bins. The problem is well known to be NP-hard. Therefore a lot of (polynomial time) approximation algorithms have been defined and analysed. We will consider the class of online algorithms where the items appear one after the other, and the algorithm has to place the items immediately and irrevocably without knowing anything about the subsequent items. One possibility to measure the effciency of an algorithm to give its asymptotic competitive ratio (ACR) which is given
as follows. Let $A$ be an arbitrary approximation algorithm, and let $I$ be an instance of the given problem. Let A($I$) and OPT($I$) denote the solution of $A$ and the optimal solution, respectively. The ACR is defned as follows:
$\displaystyle R_A^\infty = \limsup_{k\to \infty} \,\{ \max_{I} \{ A(I)/k: \mbox{\rm OPT}(I)=k\}\}$.

It is clear that online algorithms do not have enough information to produce a good packing. So the question in hand: how good can an online algorithm possibly be? In this talk we will discuss the history of lower bounds for the effciency of online bin packing algorithms.

We start with a simple example showing that for any online bin packing algorithm $A$ we have $R_A^\infty\ge 4/3$. Then using the so-called Salzer-sequences we give combinatorial proofs to verify that $R_A^\infty\ge 1.5364$. Introducing an LP formulation van Vliet (1994) improved the lower bound to 1.5401. It was
an open question for a long time whether van Vliet's result can be proved in a purely
combinatorial way. In 2012 we gave a positive answer to this question.
Moreover, we managed to improve the lower bound to 1.5403 by using a different proof technique which is interesting in its own right, and also can be extended to arrive at an improved improved lower bound for a class of semi-online bin packing algorithms.

Strukturtheorie-Seminar

Title: Lyapunov exponents for simple symmetric random walks in random potential on the integers
Speaker: Gundelinde Wiegel (Institut für Diskrete Mathematik)
Date: Wednesday, 08. Juni 2016, 10:15
Room: SR A306, Steyrergasse 30
Abstract:

Abstract: We consider a simple symmetric random walk on the integers moving in random potential. The potentials represent a random risk of dying for the RW at each sites. A measure for the riskiness of moving in this random environment are the Lyapunov exponents. They observe the long time behaviour of the probability of reaching a certain site after starting at a fixed site. There are two different ways of treating the random potentials in this observation: the annealed (or averaged) and the quenched approach. We will see that in the case of the integers we can directly relate these two approaches to each other.

Rigorosum

Title: Differential Geometry of Semidiscrete Surfaces
Speaker: W. Carl (TU Graz)
Date: 3.6.2016, 14:00-
Room: Seminarraum 2, Kopernikusgasse 24/4
Abstract:

Zahlentheoretisches Kolloquium

Title: L-functions of function fields
Speaker: Dr. Marc Munsch (Institut f. Analysis und Zahlentheorie, TU Graz)
Date: Freitag, 3. 6. 2016, 14:00 Uhr
Room: Seminarraum Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24/II, TU Graz
Abstract:

Abstract: In this talk, we will discuss function fields analogues of
some classical analytic number theoretical problems, particularly
concerning L-functions.

Probevorlesung

Title: Einführung in Galton-Watson-Prozesse
Speaker: Dr. Lorenz Gilch (Institut f. Diskrete Mathematik, TU Graz)
Date: Montag, 30. Mai 2016, 16:15 - 17:00 Uhr
Room: HS P2, Petersgasse 16/EG
Abstract:

Definition von Galton-Watson-Prozessen und -Bäumen; es werden wichtige Eigenschaften dieses Prozesstyps zusammengefasst.
Herleitung der Aussterbewahrscheinlichkeit eines Galton-Watson-Prozesses als Lösung eines Fixpunktproblems.
Grenzwertsatz für Galton-Watson-Prozesse unter Anwendung des Martingal-Konvergenzsatzes

Vortrag im Seminar für Kombinatorik und Optimierung

Title: On the spectral gap of random hyperbolic graphs
Speaker: Dieter Mitsche (Université de Nice Sophia Antipolis)
Date: Dienstag 24.5.2016, 14:15
Room: Seminarraum AE06, Steyrergasse 30, Erdgeschoss
Abstract:

Random hyperbolic graphs have been suggested as a promising model of social networks. We consider the random hyperbolic graph model as formalized by Gugelmann et al. and essentially determine the spectral gap of the normalized Laplacian. Specifically, we establish that a.a.s.~the second smallest eigenvalue of the normalized Laplacian of the giant component of the random hyperbolic graph is $\Omega(n^{-(2\alpha-1)}/\polylog(n)$, where $\frac12<\alpha<1$ is a model parameter. As a byproduct we conclude that the conductance upper bound on the eigenvalue gap obtained via Cheeger's inequality is essentially tight. We also provide a more detailed picture of the collection of node on which the bound on the conductance is attained.

Joint work with Marcos Kiwi.

Strukturtheorie-Seminar

Title: Hastings-Levitov planar aggregation model
Speaker: Vittoria Silvestri (University of Cambridge)
Date: Thursday, 09. Juni 2016, 11:15
Room: SR AE02, Steyrergasse 30, ground floor
Abstract:

In this talk I will discuss one instance of the so called Hastings-Levitov planar aggregation model, consisting of growing random clusters on the complex plane, built by iterated composition of random conformal maps. In 2012 Norris and Turner proved that in the case of i.i.d. maps the limiting shape of these clusters is a disc. I will show that the fluctuations around this asymptotic behaviour are given by a random holomorphic Gaussian field F on $\{|z|>1\}$,
of which I will provide an explicit construction. The boundary values of F perform a Gaussian Markov process on the space of distributions, which is conveniently described as the solution of a stochastic PDE. When the cluster is allowed to grow indefinitely, this process converges to the restriction of the whole plane Gaussian Free Field to the unit circle.

Festkolloquium, 2.Teil

Title: Zum Anlass des 50.Geburtstages von Herrn Univ.-Prof.Dr.Peter Grabner
Speaker: ()
Date: Montag, 23. 5. 2016
Room: Seminarraum Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24, 2.Stock, TU Graz
Abstract:

\vspace{1cm}

14:00: Joël Rivat (Aix Marseille Universit\'{e})
On the digits of prime numbers

14:45: Helmut Prodinger (Univ. of Stellenbosch)
Peter Grabner: an analysts view of combinatorics

15:30: Kaffeepause

16:00: Gregory Derfel (Ben-Gurion University of the Negev)
Diffusion on fractals and the Poincar\'{e} functional equation



[1cm]

Festkolloquium, 1.Teil

Title: Zum Anlass des 50.Geburtstages von Herrn Univ.-Prof.Dr.Peter Grabner
Speaker: ()
Date: Freitag, 13. 5. 2016
Room:
Abstract:

\vspace{1cm}

Ort: HS M „Chemie“, Kopernikusgasse 24, 2.Stock, TU Graz[3mm]
10:15: Guy Barat (Marseille)
On Numeration

11:00: Kaffeepause

11:30: Michael Drmota (TU Wien)
The Discrepancy of Generalized Van-der-Corput-Halton Sequences
[1cm]

Ort: HS BE01, Steyrergasse 30, EG, TU Graz[3mm]
14:00: Ed Saff (Vanderbilt University)
Optimal Discrete Measures for Riesz Potentials

14:45: Ian Sloan (UNSW, Sydney)
Needlet approximation on the sphere - a fully discrete version

15:30: Kaffeepause

16:00: Johann Brauchart (TU Graz)
Quasi-Monte Carlo Quadrature on the sphere

[8mm]
17:00: Prolog

[1cm]

Strukturtheorie-Seminar

Title: A functional limit law for p-rotor walk
Speaker: Wilfried Huss (TU Graz)
Date: 12.05.2016, 11:00 s.t.
Room: SR AE02, Steyrergasse 30, ground floor
Abstract:

We introduce a family of non Markovian nearest neighbor walks on $\mathbb{Z}$
called p-rotor walks, which depend on a parameter $p\in[0,1]$. For $p=1/2$ this
model is equivalent to simple random walk, and for $p=0$ we recover deterministic
rotor-router walk. We prove a functional limit law for p-rotor walk starting from
random i.i.d. rotor environment. The limit process is shown to be a doubly perturbed
Brownian motion $\mathcal{X}(t)$, which is the unique solution of the implicit
equation

$$\mathcal{X}(t) = \mathcal{B}(t) + a \sup_{s\leq t} \mathcal{X}(s) + b \inf_{s\leq t} \mathcal{X}(s),$$

where $\mathcal{B}(t)$ is standard Brownian motion, and $a, b < 1$.

This is joint work with Lionel Levine and Ecaterina Sava-Huss.

Strukturtheorie-Seminar

Title: Asymptotics and estimates of the Green function for convolution semigroups
Speaker: Dr. Tomasz Grzywny (Wroclaw University of Technology)
Date: Wednesday, 4. May 2016, 10:00 s.t.
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

We present asymptotic formulas and estimates for the Green function of isotropic unimodal convolution semigroups of probability measures on d-dimensional Euclidean space under the assumption that its Levy exponent varies regularly (including the case when it varies slowly).

The talk is based on a joint project with W. Cygan, M. Ryznar and B. Trojan.

Zahlentheoretisches Kolloquium

Title:
Speaker: ()
Date: Freitag, 29. 4. 2016, ab 14:00 Uhr
Room: SR NT02008, Kopernikusgasse 24/2.Stock
Abstract:

14:00: Markus Hittmeir, (Univ. Salzburg)
A Computational Aspect of Rational Residuosity

Abstract.} Let $k\in\N$, $p\in\PP$ and $a\in\Z$ such that $p\nmid a$. We consider a generalization of Legendre's symbol, the so called rational power residue symbol
\[
\left( \frac{a}{p} \right)_{2^k}:=\left\{\begin{array}{cl} 1, & \mbox{if there is $x\in\Z$ such that }x^{2^k}\equiv a \mod p, -1 & \mbox{else.} \end{array}\right.
\]
Let $N=pq$ be a semiprime number with large prime factors $p$ and $q$, $p\neq q$. The security of the RSA cryptosystem relies on the difficulty to compute $p$ and $q$ in the case that only $N$ is known. For $\gcd(N,a)=1$, we define $\left( \frac{a}{N} \right)_{2^k}:=\left( \frac{a}{p} \right)_{2^k}\cdot \left( \frac{a}{q} \right)_{2^k}$. In this talk, we will show that an efficient algorithm for computing this generalized Jacobi symbol would allow the efficient computation of the $2$-adic valuations $\nu_2(p-1)$ and $\nu_2(q-1)$ and, hence, of the first few bits of $p$ and $q$. We will also discuss the problem raised by this result, namely finding a reciprocity law for $\left( \frac{a}{N} \right)_{2^k}$.

[2cm]

14:45: Bruno Martin, (Univ. du Littoral C\^{o}te d'Opale)
On prime numbers with an average sum of digits

Abstract}:
Let $q\ge 2$ be an integer and $\mathcal{E}$ be the set of prime numbers $p$ whose the sum of digits in base $q$ is equal to $\left\lfloor \frac{q-1}2 \frac{\log p}{\log q}\right\rfloor$. We prove that for every irrational number $\beta$, the sequence
$( \beta p)_{p\in\mathcal{E}}$ is uniformly distributed modulo 1.

This is a joint work with Christian Mauduit and Jo\"el Rivat (Universit\'e d'Aix-Marseille).


Zahlentheoretisches Kolloquium

Title: Fibonacci Numbers which are products of two Pell Numbers
Speaker: Mahadi Ddamulira (The Abdus Salam International Centre for Theoretical Physics (ICTP), Trieste)
Date: Donnerstag, 28. 4. 2016, 14:00 Uhr
Room: SR Analysis-Zahlentheorie (NT02008), Kopernikusgasse 24, 2.Stock
Abstract:

Abstract. In this paper, we find all Fibonacci numbers which are products of two Pell numbers and all Pell numbers which are products of two Fibonacci numbers.

Vortrag

Title: An introduction to PDEs involving the fractional Laplacian: analysis and finite element approximations
Speaker: Dr. Johannes Pfefferer (TU München)
Date: Mittwoch, 27.4.2016, 9:00 Uhr
Room: TU Graz, Steyrergasse 30, 3. Stock, Seminarraum A306
Abstract:

Strukturtheorie-Seminar

Title: Universality approach to the analysis of first passage times
Speaker: Prof. Vitali Wachtel (Univ. Augsburg)
Date: Thursday, 21.April 2016, 11:00 s.t.
Room: SR AE02, Steyrergasse 30, ground floor
Abstract:

In the first part I shall describe briefly the classical approach to the study
of first passage times of random walks, which is based on the well-known duality lemma. This duality holds only for random walks with independent, identically distributed increments.

In the second part I shall present a new method, which allows one to study first passage times for a wider class of random walks. It turns out that, assuming that a random walk belongs to the domain of attraction of the Brownian motion, one can derive asymptotics for first passage times of random walk.

Zahlentheoretisches Kolloquium

Title: Decomposition of integer-valued polynomial algebras
Speaker: Dr. Giulio Peruginelli (Univ. Padova)
Date: Freitag, 15. 4. 2016, 11:30 - 12:15
Room: SR 2 des Inst. fuer Geometrie, Kopernikusg. 24, 4.Stock
Abstract:

Abstract: Let $D$ be an integral domain of quotient field $K$, $A$
a torsion-free $D$-algebra and $B=A\otimes_D K$ the extended
$K$-algebra. The set of integer-valued polynomials on $A$ is
${\rm Int}(A)=\{f\in B[X] \mid f(A)\subseteq A\}$
and the intersection of ${\rm Int}(A)$ with $K[X]$ is the ring
${\rm Int}_K(A)$. In general, ${\rm Int}(A)$ is just a left
$\Int_K(A)$-module.

We present a definition of
${\rm Int}_K$-decomposable algebras (introduced recently by Nicholas Werner)
that is applicable also to $D$-algebras that are not free as
$D$-modules: we define $A$ to be ${\rm Int}_K$-decomposable when
${\rm Int}(A) \cong {\rm Int}_K(A) \otimes_D A$.

If $D$ is a Dedekind domain
with finite residue fields, we provide multiple characterizations of
such algebras: $A$ is ${\rm Int}_K$-decomposable algebras if and only if
either one of the following equivalent conditions hold:
\begin{enumerate}
\item
for each maximal ideal $P$ of $D$, $A/PA$ is a direct sum of copies
of a matrix ring over a finite field;
\item
for each maximal ideal $P$ of $D$, the
$P$-adic completion of $A$ is isomorphic to a finite direct sum of
copies of a matrix ring over a finite unramified extension of the
$P$-adic completion of $D$.
\end{enumerate}

We also prove that if $A$ is ${\rm Int}_K$-decomposable, then $A$
must be a maximal $D$-order in $B$ and $B$ must be separable
(hence, semisimple). Moreover, if $K$ is a number field with ring
of integers $D$, then the simple components of $B$ have the same
center, which is a finite unramified Galois extension of $K$.
This is joint work with Nicholas J. Werner.

Strukturtheorie-Seminar

Title: The heat kernel for the Vladimirov Laplacian and its oscilation on the diagonal
Speaker: Prof. Alexander Bendikov (Univ. Wroclaw)
Date: Thursday, 14.April 2016, 11:00 s.t.
Room: SR AE02, Steyrergasse 30, ground floor
Abstract:

We compute the precise (oscillating) asymptotic behavior of the diagonal elements of the heat kernel for the Vladimirov Laplacian on p-adic spaces. It turns out that it is a function of finite order which is not regularly varying at infinity.

This is joint work with W. Cygan and W. Woess.

Strukturtheorie-Seminar

Title: On the Bonsall cone spectral radius and the approximate point spectrum
Speaker: Aljoša Peperko (Univerza v Ljubljani)
Date: Mittwoch 6. April 2016, 10:00 s.t.
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

We study Bonsall's cone spectral radius and the approximate point spectrum of (in general non-linear) positively homogeneous, bounded and supremum preserving maps, defined on a max-cone in a given normed vector lattice. We prove that Bonsall's cone spectral radius of such maps is always included in its approximate point spectrum. Our results apply to a large class of (nonlinear) max-type operators appearing in problems arising in certain differential and difference equations, mathematical physics and elsewhere, in particular to max type operators considered by Mallet-Parret and Nussbaum (2003).

By applying the techniques of proofs of the above result, we are also able to prove a generalization (to normed spaces and convex cones) of an (implicitly) known result that the spectral radius of a positive (linear) operator on a Banach lattice is contained in the approximate point spectrum. Under additional compactness type assumptions or for special cases of max-type operators we obtain additional results.

This is a joint work with Vladimir Müller (Institute of Mathematics, Czech Academy of Sciences).

Strukturtheorie-Seminar

Title: Mealy automata, orbit trees and the Burnside problem
Speaker: Thibault Godin (LIAFA Paris)
Date: Wednesday, 6. April 2016, 14:00 s.t.
Room: SR A306, Steyrergasse 30, 3rd floor
Abstract:

In 1902 Burnside asked a question that was to become very influential in group theory: Can a group with all elements of finite order be infinite?

This question has found a positive answer in 1964 with the work of Golod and Shafarevich, but also in 1980 with a group generated by an automaton with only 5 states and 2 letters. Then, since the 80's, automaton groups arise as a powerful source of example of interesting groups.

In this talk we will discuss the impact of the structural properties of the underlying automaton on the generated group and present a combinatorial tool, the orbit tree of an automaton, that can be used to prove that some classes of automata cannot generate infinite Burnside groups. We will also give some idea of the proofs. No prior background is required.

This is joint work with Ines Klimann and Matthieu Picantin.

Zahlentheoretisches Kolloquium

Title:
Speaker: ()
Date: Freitag, 18. 3. 2016, ab 14:00 Uhr
Room: SR NT02008, Kopernikusgasse 24/2.Stock, TU Graz
Abstract:

14:00: Leonhard Summerer, (Univ. Wien)
The method of sukcessive minima functions on behalf of the example of 2-dimensional simultaneous approximation

14:45: Antoine Marnat, (TU Graz)
Roy's Theorem and its applications

15:30: Kaffeepause

15:45: Johannes Schleischitz, (BOKU Wien)
Selected results on classical exponents of Diophantine approximation

Strukturtheorie-Seminar

Title: Biased random walk on a one-dimensional percolation cluster
Speaker: JunProf. Dr. Matthias Meiners (TU Darmstadt)
Date: Thursday., 17.3.2016, 11:00 s.t.
Room: Seminar room AE06 (STEG050), Steyrergasse 30, ground floor
Abstract:

In my talk I will introduce a one-dimensional percolation model dating back to Axelsson-Fisk and Häggström, and consider biased random walk on the infinite cluster of this model. Originally, this model has been designed to allow qualitative predictions of the behavior of biased random walk on the infinite cluster of supercritical percolation on $Z^d$

Häggström and Axelsson-Fisk have shown that biased random walk $(X_n)_n$ on the one-dimensional percolation cluster exhibits a phase transition: the linear speed $\lim_n X_n/n$ of the walk is positive iff the bias of the walk is strictly smaller than a critical bias $\lambda_c$.

I will explain that in the regime of the central limit theorem, that is, where the bias $\lambda$ is smaller than $\lambda_c/2$, the linear speed of the walk is a differentiable function of the bias $\lambda$.

(Collaboration with N. Gantert and S. Müller)

Zahlentheoretisches Kolloquium

Title: Algebraic independence results for reciprocal sums formed by powers of Fibonacci numbers
Speaker: Prof. Dr. Carsten Elsner (Fachhochschule für die Wirtschaft Hannover)
Date: Freitag, 11. 3. 2016, 14:00 Uhr
Room: SR NT02008, Kopernikusgasse 24/2.Stock
Abstract:

{\bf Abstract:}
\[\]
Let ${(U_n)}_{n\geq 0}$ be a sequence of numbers given by $U_n=(\alpha^n - \beta^n)/(\alpha - \beta)$ for $n\geq 0$, where $\alpha$ and $\beta$
are complex numbers satisfying $|\beta|<1$ and $\alpha \beta =-1$. Let $s\geq 1$ and
\[\Phi_{2s} \,:=\, {(\alpha - \beta)}^{-2s} \sum_{n=1}^{\infty} \frac{1}{U_n^{2s}} \,.\]
In a joint paper of the lecturer with Prof. Shun Shimomura and Prof. Iekata Shiokawa it is shown that for any positive integers $s_1,s_2,s_3$
corresponding to algebraic $\alpha,\beta$ with $|\beta|<1$ and $\alpha \beta =-1$ the numbers $\Phi_{2s_1},\Phi_{2s_2},\Phi_{2s_3}$ are
algebraically independent over ${\Q}$ if and only if $s_1s_2s_3\equiv 0 \pmod 2$. In particular, for $\beta=(1-\sqrt{5})/2$ and $\beta=1-\sqrt{2}$
the results on $\Phi_{2s}$ are applicable to reciprocal sums formed by powers of Fibonacci numbers $U_n=F_n$ and by powers of Pell numbers $U_n=P_n$,
respectively. In the lecture the proof of the algebraic independence of $\Phi_{2s_1},\Phi_{2s_2},\Phi_{2s_3}$ is presented for the particular case
of three even integers $2\leq s_1<s_2<s_3$.

Übersichtsvortrag

Title: The mathematics of committee decisions: The impossibility of judgment aggregation and how to avoid it
Speaker: Prof. Christian List FBA (London School of Economics)
Date: 7.3.2016, 16.15-17.45
Room: STEG050, Steyerergasse 30, Erdgeschoss
Abstract:

How can the judgments of several individuals (committee members, judges,
voters) be aggregated into collective judgments, to be endorsed by the group as a whole? To illustrate that this is a non-trivial problem, suppose that a
multi-member court has to make a decision on some conclusion (``is the
defendant liable?'') on the basis of several premises (``was there a valid contract?'', ``was there a breach?''), where the premises are jointly necessary and sufficient for the conclusion (i.e., ``liability if and only if contract and breach''). It can then happen that each premise is supported by a
majority of the judges, while the conclusion is not. This shows that the court's judgment may depend on the voting protocol used. More generally, majority voting does not guarantee logically consistent collective judgments, even when all individual judgments are consistent.


The theory of judgment aggregation offers a framework for analysing such
collective decision problems. The aim of this talk is to give an
introductory overview of that theory and to explain some of its central
impossibility and possibility results.


No prior familiarity with this topic will be presupposed. For some
optional background reading, see:

(more formal) http://personal.lse.ac.uk/list/PDF-files/ReviewPaper.pdf

(less formal) http://personal.lse.ac.uk/list/pdf-files/LogicalSpace.pdf

Zahlentheoretisches Kolloquium

Title: Divisibility of binomial coefficients by powers of two
Speaker: Dr. Lukas Spiegelhofer (TU Wien)
Date: 22. Jänner 2016, 14:00 Uhr
Room: Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz
Abstract:

\begin{abstract}
\newcommand{\bO}{\mathbf 0}
\newcommand{\bL}{\mathbf 1}
It is known that the number $a(\alpha,n)$ of binomial coefficients $\binom nt$ exactly divisible by $2^\alpha$ can be expressed using a polynomial $P_\alpha$ in block-additive functions in base $2$.
For example, we have
\[\begin{array}{ll}
a(1,n)/a(0,n)&=\tfrac 12\lvert n\rvert_{\bL\bO},
a(2,n)/a(0,n)&=-\frac 18\lvert n\rvert_{\bL\bO}+\lvert n\rvert_{\bL\bO\bO}+\frac 14\lvert n\rvert_{\bL\bL\bO}+\frac 18\lvert n\rvert_{\bL\bO}^2,
\end{array}\]
where $\lvert n\rvert_w$ is the number of times the word $w$ occurs as a subword of the base-$2$ expansion of $n$.

In this talk, we present a method for obtaining the sequence of coefficients of a given monomial in the polynomials $P_0,P_1,\ldots$ as a generating function.

In particular, we apply this method to the monomial $X_{\bL\bO}^k$ (corresponding to the term $\lvert n\rvert_{\bL\bO}^k$) and the associated sequence $\bigl(c^{(k)}_\alpha\bigr)_{\alpha\geq 0}$ of coefficients, obtaining the generating function
\[
\sum_{\alpha\geq 0}c^{(k)}_\alpha x^{\alpha}=\left(\log\left(1+\frac x2\right)\right)^k.
\]
\end{abstract}


Advanced Topics Seminar

Title: New bounds for the cp-rank in copositive optimization
Speaker: Immanuel Bomze (Universität Wien)
Date: Freitag, 22.01.2016, 10:30 Uhr
Room: Seminarraum 2 (Geometrie), 4. Stock, Kopernikusgasse 24
Abstract:

In copositive optimization, it is essential to determine the minimal number of nonnegative vectors whose dyadic products form, summed up, a given completely positive matrix (indeed, one of these vectors necessarily must be a solution to the original problem). This matrix parameter is called cp-rank. Since long, it has been an open problem to determine the maximal possible cp-rank for any fixed order. Now we can refute a twenty years old conjecture and show that the known upper bounds are asymptotically equal to the lower ones.

Strukturtheorie-Seminar

Title: A Garden of Eden theorem for hyperbolic homeomorphisms
Speaker: Prof. Tullio Ceccherini-Silberstein (Rome)
Date: Thursday., 21.1.2016, 11:00 s.t.
Room: Seminar room C307, Steyrergasse 30, 3rd floor
Abstract:

Using techniques from symbolic dynamics, we prove a Garden of Eden type theorem for some hyperbolic homeomorphisms of a compact metrizable space (e.g. Anosov diffeomorphisms). This is a recent joint work with Michel Coornaert

Vortrag im Seminar für Kombinatorik und Optimierung

Title: Bootstrap percolation on geometric inhomogeneous random graphs
Speaker: Christoph Koch (TU Graz)
Date: Dienstag 19.1.2016, 14:15
Room: Seminarraum C208, Steyrergasse 30, 2. Stock
Abstract:

Recently Bringmann, Keusch, and Lengler introduced a new random graph model -- geometric inhomogeneous random graphs (GIRGs) -- possessing many of the characteristic properties of complex real-world networks (Power-law degree distribution, small diameter, etc.). Each vertex consists of a geometric position and a weight and any two vertices $u,v$ are connected by an edge independently with some probability $p_{u,v}$ depending on their weights and relative position. In particular, GIRGs generalise the well-studied model of hyperbolic random graphs and facilitate their analysis by stripping off most of the technical details.

In this talk we investigate the evolution of a well-known infection process called bootstrap percolation with localised initial infection on GIRGs. Given some infection parameter $r>1$ and a ball $B_0$ of volume $\nu$ we initially infect any vertex lying in $B_0$ with some probability $p_0$. And then round after round, the infection spreads to all those still uninfected vertices which have at least $r$ infected neighbors. Once a vertex becomes infected, it remains so forever. We show that this process exhibits a threshold behaviour in terms of $p_0$, in other words, there is a critical probability $p_c=p_c(\nu)$ such that the following holds: If $p_0/p_c\to\infty$ then the process starts to accelerate very quickly and eventually infects a large proportion of all vertices; while if $p_0/p_c\to 0$ then it stops without infecting substantially more vertices than those which were infected initially.

This extends some results by Candellero and Fountoulakis on bootstrap percolation with global initial infection on hyperbolic random graphs.

This is joint work with Johannes Lengler.

Strukturtheorie-Seminar

Title: Fock space associated to Coxeter group of type B
Speaker: Wiktor Ejsmont (Uniwersytet Wrocławski)
Date: Thursday, 14.1.2016, 11:00 s.t.
Room: Seminar room C307, Steyrergasse 30, 3rd floor
Abstract:

We will discuss generalized Gaussian processes arising from Coxeter groups of type B and D.

Strukturtheorie-Seminar

Title: Counting walks in graphs
Speaker: Prof. Dragan Stevanovic (Univ. Primorska, Koper, and Kuwait University)
Date: Thursday, 7.1.2016, 11:00 c.t.
Room: Seminar room C307, Steyrergasse 30, 3rd floor
Abstract:

A classical result states that the number of closed walks of length k in a graph G is equal to the trace of the k-th power of its adjacency matrix A. If G is connected, its largest eigenvalue $\lambda_1$ has maximum absolute value among all eigenvalues of A by the Perron-Frobenius theorem, so that
$$
\lambda_1=\lim_{k\to\infty}\sqrt[2k]{\mathrm{tr}(A^{2k})}.
$$
Let $G\preccurlyeq H$ denote that the number of closed walks of length~$k$ in~$G$ is less than or equal to the number of closed walks of length~$k$ in~$H$ for infinitely many values of~$k$. Hence $G\preccurlyeq H\,\Rightarrow\,\lambda_{G,1}\leq\lambda_{H,1}$.

We present here a general graph composition, the so-called {\em multiple coalescence}, which enables one to count closed walks in composed graph in terms of closed walk counts of constituent graphs. As a result, multiple coalescence preserves the relation $\preccurlyeq$ under natural and mild assumptions on its constituents. We will showcase the use of multiple coalescence in the resolution of Belardo, Li Marzi and Simi\'c's conjectured generalizations of the Li-Feng lemmas and apply them to study spectral radius of rooted product of graphs. We will also discuss current obstacles in applying multiple coalescence to attack the 1991 conjecture of Cvetkovi\'c and Rowlinson on the maximum spectral radius of outerplanar graphs.