### Talks in 2012

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Random Walks on critical Percolation-Trees

**Speaker:**Florian Sobieczky (University of Denver)

**Date:**18.12. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

Bounds for the expected return probability of the delayed random walk on

finite clusters of an invariant percolation on transitive unimodular

graphs are derived. They are particularly suited for the case of critical

Bernoulli percolation and the associated heavy-tailed cluster size

distributions. The upper bound relies on the fact that cartesian products

of finite graphs with cycles of a certain minimal size are Hamiltonian.

For critical Bernoulli bond percolation on the homogeneous tree this bound

is sharp. The asymptotic type of the expected return probability for large

times t in this case is of order of the 3/4'th power of 1/t.

#### Joint Seminar

**Title:**Lumped Markov chains and entropy rate preservation

**Speaker:**Bernhard Geiger and Christoph Temmel (TU Graz)

**Date:**10 Dez, 16:00

**Room:**IDEG134

**Abstract:**

A lumping of a Markov chain is a coordinate-wise projection of the chain. We characterize the entropy rate loss of a lumping of a stationary Markov chain on a finite state space in two ways. First, by the asymptotic ratio of the number of trajectories with positive weight between the original and the lumped chain. Second, by the reconstructability of original trajectories from their images under the lumping. Every non-trivial lumping of a Markov chain with positive transition matrix incurs an entropy rate loss. We give sufficient conditions on the non-positive transition matrix and the lumping to preserve the entropy rate. In the sparse setting we state sufficient conditions on the lumping to both preserve the entropy rate and result in a k-th order homogeneous Markov chain.

#### Kolloquium: Mathematische Methoden in den Natur- und Ingenieurwissenschaften

**Title:**Gauss, Jacobi, Seidel, Richardson, Krylov: The Invention of Iterative Methods

**Speaker:**Univ.-Prof. Dr. Martin J. GANDER (Universität Genf)

**Date:**Freitag, 7.12.2012, 16:00 Uhr

**Room:**TU Graz, Steyrergasse 30, 3. Stock, Seminarraum C307

**Abstract:**

#### Vortragseinladung

**Title:**Optimal Transport, Model-Indepedence, and Trajectorial Inequalities.

**Speaker:**Mathias Beiglböck (Universität Wien)

**Date:**Freitag, 7.12.2012, 14:15 Uhr

**Room:**Seminarraum A206, Steyrergasse 30, 2.Stock, Geodäsie

**Abstract:**

Abstract:

We will explain a recently discovered connection between Optimal

Transport and the areas of model independence / martingale

inequalities in probability. This link has a number of fruitful

consequences. For instance, the duality theorem from optimal transport

leads to new super-replication results. Optimality criteria from the

theory of mass transport can be translated to the martingale setup and

allow to characterize minimizing/maximizing models in finance.

Moreover, the dual viewpoint provides new

insights to the classical inequalities of Doob and Burkholder-Davis-Gundy.

#### Strukturtheorie-Seminar

**Title:**The Bee in the Balloon: Recurrence on Growing Subgraphs

**Speaker:**Florian Sobieczky (University of Denver)

**Date:**6.12.2012, 15:00

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

What is the rate at which the radius of a ball has to be continuously increased such that a diffusing particle, reflected back inside when hitting the boundary, becomes transient? It is shown that the question has the same answer for brownian motion in three-dimensional euclidean space and for simple random walk on the euclidean lattice: $\sim t^{1/d}$.

#### DK Seminar

**Title:**Discretized rotation has infinitely many periodic orbits

**Speaker:**Attila Pethoe (Debrecen)

**Date:**21.12.2012, 10:30

**Room:**HS Thermoprozesstechnik, Montanuniversität Leoben

**Abstract:**

After the lecture of Attila Petho in Leoben, there will be a lunch in a nearby

restaurant.

#### Minikurs/Intensivseminar

**Title:**Fortsetzungen von Quasirandtripeln

**Speaker:**Till Micheler (Institut für Mathematik, TU Berlin)

**Date:**4.12. 13:00-14:00 im A206, 5.12. 8:15-9:45 im A111

**Room:**und 6.12. 13:00-16:00 im A306

**Abstract:**

Quasirandtripel sind ein modernes Werkzeug in der

Erweiterungstheorie von symmetrischen Operatoren in Hilberträumen

mit vielen konkreten Anwendungsmöglich- keiten, z.B. im Bereich der

elliptischen partiellen Differentialgleichungen.

In diesem Intensivseminar diskutieren wir

Fortsetzungen und Fortsetzbarkeit von Quasirandtripeln, das heisst

wir betrachten hinreichende und notwendige Bedingungen, unter welchen

sich die Randabbildungen eines Quasirandtripels

auf den maximalen Definitionsbereich des zugrundeliegenden Operators

fortsetzen lassen. Dadurch werden in natürlicher Weise

auch das gamma-Feld und die Weylfunktion des Quasirandtripels

fortgesetzt, und es gelten erweiterte Krein'sche Formeln.

#### Strukturtheorie-Seminar

**Title:**Rate of convergence and Edgeworth-type expansion in the entropic central limit theorem

**Speaker:**Gennadii Chistyakov (Universität Bielefeld)

**Date:**29.11.2012, 15:00

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

An Edgeworth-type expansion is established for the entropy distance to the class of normal distributions of sums of i.i.d. random variables or vectors, satisfying minimal moment conditions.

#### Kolloquium

**Title:**Festkolloquium anlässlich des 80. Geburtstages von em. Univ. Prof. Dr. Ulrich DIETER

**Speaker:**()

**Date:**Freitag, 30. November 2012, 14.00 Uhr

**Room:**HS D, Kopernikusgasse 24/III

**Abstract:**

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**The H-elimination random graph process

**Speaker:**Tamas Makai (Institut für Optimierung und Diskrete Mathematik, TU Graz)

**Date:**27.11. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

Consider the random graph process which starts out from the complete graph on $n$

vertices and in every step of the process an edge, selected uniformly at random from

the set of edges which are contained in a copy of a fixed graph $H$, is removed. The

process stops after no more copies of $H$ are present. This process is called the

$H$-elimination random graph process. In 1990 Bollob\'as and Erd\H{o}s asked for the

typical number of edges present in the graph created by this process when $n$ is

large. We answer this question in case $H$ belongs to a special class of graphs,

namely the strictly 2-balanced graphs.

#### Mathematisches Kolloquium

**Title:**Integral Geometry and Isoperimetric Inequalities

**Speaker:**Franz Schuster (TU Wien)

**Date:**23.11.2012, 14:30 (Kaffee Institut f. Geometrie), 15:00 (Vortrag Hörsaal A)

**Room:**HS A, Kopernikusgasse 24, 1. Stock

**Abstract:**

This lecture presents some of the fascinating developments which happened in Integral Geometry in the last years, establishing connections to Differential Geometry and Functional Analysis. The concept of {\em valuation} is central to this development, which means functions $\phi$ on the set of convex bodies (or of more general subsets of ${\mathbb R}^n$) which have values in a certain abelian semigroup and which enjoy the property \[\phi(K) + \phi(L) = \phi(K \cup L) + \phi(K \cap L)\] whenever all of $K$, $L$, $K \cup L$ are convex. Valuations, as generalizations of measures, have long played an important role in geometric analysis, starting with Dehn's solution of Hilbert's third problem and the theory of dissections of polytopes. In the last 5 to 10 years strong connections between affine geometry and valuations emerged: A series of fundamental operators on convex bodies, like the projection body and intersection body, could be classified in terms of the valuation property and compatibility with affine mappings. These results have been applied to the theory of affine isoperimetric inequalities and in particular were used to significantly sharpen several classical inequalities of Euclidean geometry.

#### Strukturtheorie-Seminar (Korrektur)

**Title:**HIERARCHICAL LAPLACIANS: TWO EXAMPLES

**Speaker:**Prof Alexander Bendikov (Univ. Wroclaw, Polen)

**Date:**Donnerstag, 22.11.2012, 15 Uhr

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

We consider two examples of Markov generators defined on a discrete group which is an infinite sum of cyclic groups and give the precise asymptotic behavior at

infinity of the corresponding return probability functions. These results,

in turn, give sharp bounds on the corresponding heat kernels.

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Higher Inclusion Matrices

**Speaker:**Yury Person (Institut für Mathematik, FU Berlin)

**Date:**20.11.2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

Abstract:

Let $n\ge r \ge s \ge 0$. The higher inclusion matrix $M_s^r({ \left[n\right]\choose r})$ is a $\{0,1\}$-matrix whose

rows are indexed by all $r$-element subsets of $\left[ n\right]:=\{1,2,\ldots, n\}$ and and columns

are indexed by all $s$-subsets of $\left[n\right]$ and the entry corresponding to an $r$-set $R$ and an $s$-set $S$ is $1$ if $S \subseteq R$ and $0$ otherwise.

Gottlieb's theorem from 1966 states that $M_s^r({\left[n\right]\choose r})$ has the rank

$\min\{{n\choose r}, {n \choose s}\}$ over $\mathbb{Q}$.

Keevash asked how many rows one has to delete from $M_s^r({\left[n\right] \choose r})$ to reduce its rank by $1$. We answer his

question for large $n$ and study some generalizations of this problem. Joint work with Codru{\c t} Grosu and Tibor Szab\'o.

#### Vortrag

**Title:**Subdivision in shift-invarianten Räumen

**Speaker:**Kurt Jetter (Univ. Hohenheim, Stuttgart)

**Date:**Montag 19.11.2012, 11:00 Uhr

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

**Abstract:**

Shift-invariante Räume und ihre Approximationseigenschaften in Bezug auf

wichtige Klassen von Funktionenräumen spielen in der Angewandten Mathematik

und in der Signalverarbeitung eine zentrale Rolle. Erfüllen die Generatoren

solcher Räume zusätzlich eine Zwei- oder Mehr-Skalen-Gleichung, so sind

diese Räume und ihre skalierten Versionen die Grundlage für

Multiskalen-Analysen, wie sie z.B. bei Wave\-let-Zerlegungen oder bei

allgemeineren Frame-Darstellungen sehr effizient eingesetzt werden.

Der Vortrag führt zunächst in die Struktur shift-invarianter Räume und

deren Approximationseigenschaften ein. Anschließend wird der Spezialfall

des Vorliegens einer Zwei-Skalen-Gleichung behandelt und der Zusammenhang

mit dyadischen Subdivisionsverfahren aufgezeigt.

Anschließend werden zwei Themenbereiche herausgegriffen, in denen der

Vortragende --- zusammen mit Koautoren --- in letzter Zeit spezielle Fragen zur

Subdivision aufgegriffen und abschließend bearbeitet hat:

-- Polynomiale Reproduktion und Box-Spline-Generatoren für gewisse

bivariate Varietäten.

-- Nichtnegative Subdivision und ihr Bezug zu endlichen nichtstationären

Markov-Prozessen.

\begin{enumerate}\itemsep-\parsep\footnotesize

\item K. Jetter und G. Plonka, A survey on $L_2$-approximation orders from

shift-invariant spaces, in: {\it Multivariate Approximation and

Applicatons}, N. Dyn et al., eds., pp.

73--111, Cambridge University Press, 2001.

\item M. Charina, C. Conti, K. Jetter und G. Zimmermann, Scalar multivariate

subdivision schemes and box splines, {\it Computer Aided Geometric Design}

{\bf 28} (2011), 285--306.

\item K. Jetter und X. Li, SIA matrices and non-negative subdivision, {\it

Results Math.} (2012).

\end{enumerate}

#### Zahlentheoretisches Kolloquium

**Title:**

**Speaker:**()

**Date:**Freitag, 16.11.2012

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

{\bf 14:15: Daniel Dombek} (Czech Technical Univ. Prag)

{ On the generalizations of the unit sum number

problem (joint work with Lajos Hajdu, Attila Pethõ)}[3mm]

Abstract: In this contribution we consider representations of algebraic

integers of a number field as linear combinations of units with

coefficients from a fixed small set, and as sums of elements with

bounded norms. Presented theorems can be viewed as results

concerning a generalization of the so-called unit sum number

problem. Extending previous related results we also give an upper

bound for the length of arithmetic progressions of $t$-term sums of

algebraic integers with bounded norms.

{\bf 14:45: Tomás Vávra} (Czech Technical Univ. Prag)

{ Arithmetics in number systems with negative

quadratic Pisot base}[3mm]

Abstract: We study $(-\beta)$-numeration systems as introduced by S. Ito and

T. Sadahiro in 2009. We are interested in the set $\mathbb

Z_{-\beta}$ of $(-\beta)$-integers, i.e. the numbers whose

$(-\beta)$-expansion does not contain fractional digits. The

results about the number of fractional digits arising when summing

$(-\beta)$-integers can be extended from the class of quadratic

Pisot units $\beta$ to the non-unit case. We also comment on

exceptional arithmetic and geometric properties of a class of bases

$-\beta$ where $\beta^r=m\beta^{r-1}+\cdots + m\beta+m$, $r\geq 2$,

$m\geq 1$.

{\bf 15:15: Manfred Madritsch} (Université de Lorraine, Nancy)

{ Van der Corput sets}[3mm]

Abstract: A set $H$ of positive integers is a van der Corput set (or a vdC set)

if for any sequence $(x_n)_{n\in\mathbb{Z}}$ of real numbers, and for each

$h\in H$, the sequence $(x_{n+h}-x_n)_{n\in\mathbb{Z}}$ is uniformly

distributed mod 1, in which case the sequence $(x_n)_{n\in\mathbb{Z}}$ is

uniformly distributed mod 1. The aim of the present talk is on the one

hand to link this notion to others like recurrent sets or sets forcing

continuity. On the other hand constructions of vdC sets are

given. Finally extensions of this questions to sets in $\mathbb{Z}^d$ are considered.

#### Zahlentheoretisches Kolloquium

**Title:**

**Speaker:**()

**Date:**Donnerstag, 15.11.2012

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

{\bf 16:15: Andrej Dujella} (Univ. of Zagreb)

{ Elliptic curves with large torsion and positive rank

over number fields of small degree}

{\bf 16:45: Tomislav Pejkovic} (Univ. of Zagreb)

{ An inequality for values of Koksma's function of two

algebraically dependent p-adic numbers}

{\bf Kaffeepause}

{\bf 17:30: Vinko Petricevic} (Univ. of Zagreb)

{ Householder's approximants and continued fraction expansion

of quadratic irrationals}

#### Strukturtheorie-Seminar

**Title:**Convergence in Norm for Non-Commutative Central Limit Theorems

**Speaker:**Octavio Arizmendi (Universität des Saarlandes)

**Date:**15.11.2012, 15:00

**Room:**Seminarraum C208, Steyrergasse 30/II

**Abstract:**

In this the talk I will explain how to use cumulants to give a simple proof of an instance of the so-called superconvergence of normalized sums of free random variables. Namely, that the operator norm of normalized sums of bounded free random variables with mean 0 and variance 1, converge to 2. Moreover, our approach generalizes in a straightforward way to monotone and boolean independence and q-convolution. This is a joint work with Carlos Vargas.

#### Strukturtheorie-Seminar

**Title:**Self-similar groups: constructions, applications and open problems

**Speaker:**Dr. Daniele D'Angeli (Vila Real, Universidade UTAD, Portugal)

**Date:**Dienstag, 13.11.2012, 10:45

**Room:**SR C307, Steyrergasse 30, 3. Stock

**Abstract:**

Self-similar groups act by automorphisms on rooted trees or, equivalently, are generated by (finite) automata. Such groups have been used to find groups with exceptional and exotic properties, for example the Grigorchuk group, the first group with intermediate growth, is self-similar. In this talk I want to describe some constructions related to such groups that have applications in combinatorics, dynamics and probability. I also plan to present a list of new developments and open problems.

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**On the tree-packing conjecture of Gyarfas and Lehel

**Speaker:**Anusch Taraz (Zentrum Mathematik, TU München)

**Date:**13.11. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

In 1976, Gyarfas and Lehel made the somewhat stunning conjecture that any family of trees $T_1,T_2,\ldots T_n$, with

$1,2,\ldots, n$ vertices respectively, can be packed in an edge-disjoint manner into the complete graph on n vertices.

This conjecture is still open.

In this talk I will sketch a proof for a slightly weakened version of this conjecture, where we only consider

trees of bounded maximum degree and allow the complete graph to have an additional $o(n)$ vertices.

The proof uses tree-indexed random walks controlled by the nibble method and is joint work with J.Böttcher, J.Hladky and D.Piguet.

#### Seminar of the Doctoral School

**Title:**Doctoral Day

**Speaker:**()

**Date:**9.11.2011, 10:13-12:30

**Room:**Seminarraum 2, Inst. f. Geometrie

**Abstract:**

10:30 T. T. Luong: On a class of pseudo-analytic functions: representations, generalizations and applications

11:00 M. Juhos: Contributions to a mathematically stringent stochastics course in High School (AHS-Oberstufe)

11:30 coffee and refreshments

12:00 G. Peralta: Smooth Global Solution to a 2 × 2 Hyperbolic System on a Bounded Interval with Damping

#### Zahlentheoretisches Kolloquium

**Title:**

**Speaker:**()

**Date:**Freitag, 9.November 2012

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

{\bf 14:15: Hansjörg Albrecher} (Université de Lausanne)

{ Connecting ruin theory and queueing theory}

{\bf 15:15: Petra Tadic} (TU Graz)

{ Injectivity of the specialization homorphism of elliptic curves over fields of rational functions over number fields

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Knapsack Problems with Conflict and Forcing Constraints on Special Graphs

**Speaker:**Ulrich Pferschy (Institut für Statistik und Operations Research, Universität Graz)

**Date:**6.11. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

We consider the classical 0-1 knapsack problem and add binary constraints for

pairs of items. These can be either conflict constraints stating that certain pairs of items cannot be simultaneously contained in a feasible solution, or forcing constraints requiring that at least one of the two items of each given pair must be included in the knapsack. These constraints can be represented by a conflict resp.\ forcing graph $G=(V,E)$, where each item $j$ corresponds to a vertex $v_j\in V$ and an edge $e=(v_i,v_j)\in E$

indicates a binary constraint between items $i$ and $j$.

Note that our model can be seen as a weighted independent set resp.\ vertex cover problem with an additional budget constraint.

In this talk we will concentrate on the identification of special graph classes

as conflict resp.\ forcing graphs which permit

(Fully) Polynomial Approximations Schemes ((F)PTASs).

In particular, we will show that chordal graphs and graphs of bounded treewidth

allow an FPTAS for both problem versions.

Then we present a PTAS for planar conflict graphs based on the method by Baker.

In contrast to this positive approximability result,

the knapsack problem with a planar forcing graph is inapproximable.

Finally, we also develop dynamic programming schemes

allowing an FPTAS for a number of other graph classes defined

by the exclusion of certain induced subgraphs.

(Joint work with Joachim Schauer)

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Improving Christofides' Algorithm for the s-t Path TSP

**Speaker:**Hyung-Chan An ( Theory of Computation Laboratory, EPFL, Lausanne)

**Date:**30.10. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

Abstract:

We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a

shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had

been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of (1+sqrt(5))/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this

paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

This is joint work with Bobby Kleinberg and David B. Shmoys.

#### Strukturtheorie-Seminar

**Title:**Spectral properties of differential operators on metric graphs

**Speaker:**Prof. Jussi Behrndt (TU Graz)

**Date:**25.10.2012, 15:00 Uhr

**Room:**Seminarraum C208 (Steyrergasse 30/III)

**Abstract:**

We discuss some elementary spectral properties of differential operators on metric graphs. Our point of view is inspired by abstract methods from extension and perturbation theory of symmetric and selfadjoint operators in Hilbert spaces. We also plan to discuss a related inverse problem: Does the Dirichlet-to-Neumann map (defined on the boundary of a compact metric graph) contain the complete spectral information of the Kirchhoff Laplacian, and hence determines this operator uniquely up to unitary equivalence?

#### Kolloquiumsvortrag

**Title:**Der Zauberer von Budapest -- Paul Erd\H{o}s and the Rise of Discrete Mathematics

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

**Date:**19.10.2012, 14:30

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

**Abstract:**

Abstract:

The twentieth century saw the elevation of Discrete Mathematics from ``the slums of topology'' (one of the more

polite expressions!) to its current highly regarded position in the mathematical pantheon. Paul Erd\H{o}s played

a key role in this transformation. I will discuss some key results, possibly including:

(i) Ramsey Theory.

In 1946 Erd\H{o}s showed that you could two-color the complete graph on $n$ vertices so as to avoid a

monochromatic clique of size $k$, when $n$ was exponential in $k$. To do it, he introduced the Probabilistic

Method.

(ii) Random Graphs.

In 1960 Erd\H{o}s, with Alfr\'ed R\'{e}nyi, showed that the evolution of the random graph undergoes (in modern

language) a phase transition when the number of edges approaches half the number of vertices.

(iii) Number Theory.

In 1940 Erd\H{o}s, with Marc Kac, showed that the number of prime factors of $n$ satisfies (when appropriately

defined) a Gaussian distribution, Amazing!

Anecdotes and personal recollections of Paul Erd\H{o}s will be sprinkled liberally throughout the presentation.

#### Mathematisches Seminar Leoben

**Title:**Rauzy fractals with countable fundamental group

**Speaker:**MSc. Timo Jolivet (LIAFA, Université Paris Diderot)

**Date:**16.10.2012, 11:30-12:30

**Room:**HS Thermoprozesstechnik, Leoben

**Abstract:**

#### Mathematisches Seminar Leoben

**Title:**A review on Pisot conjecture, coincidence conditions and related graphs

**Speaker:**Prof. Anne Siegel (IRISA, CNRS, Université de Rennes)

**Date:**16.10.2012, 10:30-11:30

**Room:**HS Thermoprozesstechnik, Leoben

**Abstract:**

#### Vortrag beim NAWI-Tag

**Title:**Evolutionary Game Theory and the Emergence of Cooperation

**Speaker:**Karl Sigmund (Univ. Wien)

**Date:**2.10.2012, 14:30

**Room:**Alte Univ., Hofgasse 14

**Abstract:**

{\bf Programme of NAWI Day}

13:00 Registration and Welcome

14:00 Opening

14:30 Invited lecture by Karl Sigmund

15:30 NAWI Graz Highlights

16:00 Coffee Break

16:30 NAWI Graz Highlights

17:45 Poster Session

Registration until September 17 under info@nawigraz.at!

#### Zahlentheoretisches Kolloquium

**Title:**Counting lattice points and o-minimal structures

**Speaker:**Fabrizio Barroero (TU Graz)

**Date:**Montag, 1. 10. 2012, 16:15 Uhr (ACHTUNG: geänderte Beginnzeit!!)

**Room:**Seminarraum A206, Steyrergasse 30, 2.Stock, Geodäsie

**Abstract:**

Let $\Lambda$ be a lattice in $\mathbb{R}^n$ and $Z\subseteq

\mathbb{R}^{m+n}$ a parameterized family of subsets $Z_T$ of

$\mathbb{R}^n$. Using o-minimal structures we give an estimate for the

number of points of $\Lambda$ in $Z_T$ for a quite general class of

families $Z$.

This is joint work with Martin Widmer.

#### Mathematisches Kolloquium

**Title:**Connectivity of random discrete structures

**Speaker:**Tomasz \L uczak (Adam Mickiewicz University, Pozna\'n, Poland)

**Date:**27.9. 2012, 11:30, davor Kaffeepause ab 11:00 im SR C208

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

**Abstract:**

\vspace{2cm}

How to measure the connectivity of a discrete structure,

in particular, how the connectivity of a structure which is obtained

as a result of a random process changes when its density grows?

In the talk we discuss this problem presenting some old and

a few recent results on different models of random graphs, random groups,

and random simplicial complexes.

\vspace{2cm}

#### Strukturtheorie-Seminar

**Title:**Ricci curvature, local clustering and spectrum of finite graphs

**Speaker:**Shiping Liu (MIS MPI Leipzig)

**Date:**Dienstag, 18. September 2012, 10:30

**Room:**Seminarraum C307, Steyrergasse 30, 3. Stock

**Abstract:**

In this talk, I will introduce the Ricci curvature notion defined by Ollivier using transportation distance on the graph setting. Then I discuss its relation with local clustering coefficient of a graph, or the number of triangles, and further the number of cycles. This relation leads us to an estimate of the spectrum of the normalized Laplace operator in terms of Ollivier's Ricci curvature.

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Non-commutativity and Rota's bases conjecture

**Speaker:**Martin Loebl (Charles University Prague)

**Date:**4.9. 2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

I plan to present a reason why Rota's bases conjecture 'should' be true

also for n odd. For n even such reason is Alon-Tarsi latin squares

conjecture.

(Joint work with Ron Aharoni)

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**Submodular Optimization and Approximation Algorithms

**Speaker:**Satoru Iwata (Research Institute for Mathematical Sciences, Kyoto University)

**Date:**14.8.2012, 14:15

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

Submodular functions are discrete analogue of convex functions, arising in various fields of applied

mathematics including game theory, information theory, and queueing theory. This talk aims at providing

an overview on fundamental properties of submodular functions and recent algorithmic developments of

their optimization and approximation. Most efficiently solvable combinatorial optimization problems are

closely related to submodular function minimization, for which the ellipsoid method had been the only

polynomial algorithm until combinatorial strongly polynomial algorithms appeared. In contrast, for

submodular function maximization, which is NP-hard and known to refuse any polynomial algorithms,

constant factor approximation algorithms have been developed with applications to combinatorial auction,

machine learning, and social networks. An efficient method for approximating submoduar functions

everywhere leads to a generic framework of designing approximation algorithms for combinatorial

optimization problems with submodular costs. In some specific cases, however, one can devise better

approximation algorithms.

#### Vortrag

**Title:**On the Structure of Anisotropic Frames

**Speaker:**Prof. Philipp Grohs (Seminar für angewandte Mathematik, ETH Zürich)

**Date:**19.7.2012, 14:30 Uhr

**Room:**Chemie-Hörsaal M, Kopernikusgasse 24, 2. Stock

**Abstract:**

Anisotropic frame systems such as shearlets and curvelets have had a profound impact on applied mathematics in the last decade, the main reason being their superior ability to optimally resolve anisotropic structures such as edges in images. By now there exists a whole zoo of such constructions among which we mention second generation curvelets, bandlimited shearlets and compactly supported shearlets, all based on a parabolic dilation operation.

These systems share similar properties; this is usually proven in a case-by-case study for each different construction. In this talk I will introduce the concept of parabolic molecules which allows for a unfied framework encompassing all known anisotropic frame constructions based on parabolic scaling. The main result is that, roughly speaking, all such systems share the same approximation properties. A consequence is that we can at once deduce all the desirable approximation properties of curvelets for virtually any other system based on parabolic scaling.

This is joint work with Gitta Kutyniok.

#### Focussed meeting

**Title:**The Shape of Branching Random Walk

**Speaker:**Daniela Bertacchi (Univ. Milano - Bicocca) Elisabetta Candellero (TU Graz) Steven P. Lalley (Univ. Chicago) Francois Ledrappier (Univ. Notre Dame) Sebastian Müller (Univ. Aix - Marseille) Maura Salvatori (Univ. Milano) Fabio Zucca (Politecnico di Milano) ()

**Date:**9.-13. Juli 2012

**Room:**Seminarraum C307, Steyrergasse 30, 3. Stock

**Abstract:**

Talks on Monday - Wednesday (9-11 July)

More details will follow.

#### Vortrag

**Title:**Geometric Curve Subdivision

**Speaker:**Prof. Kai Hormann (Univ. Lugano)

**Date:**6.7.2012, 09:00 Uhr

**Room:**Seminarraum 2, Kopernikusgasse 24/4

**Abstract:**

While linear subdivision schemes for curves and surfaces are well-understood by now, we still have but a few tools for analyzing the non-linear setting, although non-linear schemes often yield better results than their linear counterparts. In this talk we discuss a geometric condition which guarantees that a nonlinear interpolating subdivision scheme produces tangent continuous limit curves. As an example, we present two non-linear variants of the classical 4-point scheme which satisfy this condition. We further demonstrate some ideas for generating limit curves with higher orders of smoothness.

#### Strukturtheorie-Seminar

**Title:**Freeness from random matrices: some probabilistic consequences

**Speaker:**Serban Belinschi (University of Saskatchewan)

**Date:**Mittwoch, 4.Juli 2012, 15:00 c.t.

**Room:**Seminarraum C307, Steyrergasse 30, 3. Stock

**Abstract:**

Probably the most important 'probabilistic' result in free probability is the celebrated asymptotic freeness result of Voiculescu, obtained in the early '90s: independent unitarily invariant random matrices are asymptotically free

as their size tends to infinity. Since then, free probability and random matrix theory have benefited massively from each other's tools and results. In this talk we shall give a brief function-analytic perspective on Voiculescu's asymptotic freeness result and show how this perspective allows one to analyze the asymptotic behaviour of certain individual eigenvalues of large random matrices.

#### (Korrektur: 4. Juli statt Juni)

**Title:**Stability of spectral types for Galton Watson trees

**Speaker:**Dr. Matthias Keller (Univ. Jena)

**Date:**Mittwoch, 4. Juli 2012, 14 Uhr c.t.

**Room:**Seminarraum C307, Steyrergasse 30, 3. Stock

**Abstract:**

In general, already small (but extensive) perturbations change the spectral types of an operator significantly. However, if the dimension of the underlying model is high enough more stability can be expected. We present a recent result dealing with (multi-type) Galton Watson trees that are close in distribution to a tree of finite cone type. In this case a large part of absolutely continuous spectrum of the deterministic tree is preserved in the random trees.

#### Zahlentheoretisches Kolloquium

**Title:**Dimension theory of mixed polynomial and power series rings

**Speaker:**Mi Hee Park (Chung-Ang University, Seoul, Korea)

**Date:**Freitag, 22.Juni 2012, 14:30 Uhr (NEUE BEGINNZEIT!!)

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

We consider the mixed polynomial and power series ring extensions,

or, for short, mixed extensions. A mixed extension over a ring $R$

in variables $x_1, \cdots, x_n$ is denoted by $R[x_1]\!]\cdots

[x_n]\!]$, where each $[x_i]\!]$ is fixed as either $[x_i]$ or

$[\![x_i]\!]$. One extreme is the polynomial extension $R[x_1,

\cdots, x_n]$ and the other extreme is the power series extension

$R[\![x_1, \cdots, x_n]\!]$. The motivation for our work comes

from the following question raised by Robert Gilmer and Jim

Coykendall: Let $R$ be a commutative ring with identity. When

$\text{dim} (R[\![x]\!])<\infty$, is $\text{dim} (R[\![x]\!])\leq

2(\text{dim}\, R) +1$? We answer the question in the negative by

computing the Krull dimension of mixed extensions over a

Pr\"{u}fer domain. We also discuss similarities and differences

among several mixed extensions over fields. Especially, given a

field extension $K\subset L$, we recall the algebraicity of the

extension $K[x_1]\!]\cdots [x_n]\!]\hookrightarrow L[x_1]\!]\cdots

[x_n]\!]$ and then compute the dimension of its generic fiber

ring. Also, we characterize the field extensions $K\subset L$ such

that the prime spectra $\text{Spec}(L[x_1]\!]\cdots [x_n]\!])$ and

$\text{Spec}(K[x_1]\!]\cdots [x_n]\!])$ are homeomorphic.

#### Vortrag

**Title:**Farey fraction spin chains and Gauss-Kuz'min statistics for quadratic irrationals

**Speaker:**Alexey Ustinov (Russian Academy of Sciences)

**Date:**20.6.2012, 12:30-13:30

**Room:**Seminarraum 2, Kopernikusgasse 24/IV

**Abstract:**

Farey fraction spin chains were introduced by P. Kleban and A. E. Özlük in 1999. Let $A={ 1 \ 0\choose 1 \ 1} $ and $ B={ 1 \ 1 \choose 0 \ 1}$. Recently F.~P.~Boca proved the following asymptotic formula for the number of spin chains with bounded trace (energy)

$$

\Psi(N) = |\{C=A^{a_1}B^{a_2}A^{a_3}\ldots:\

3\le{\rm Tr}\,C\le N \} |

= N^2(c_1\log N+c_0)+{O}_{\varepsilon}(N^{{7}/{4}+\varepsilon}).

$$In the talk the sharper result

$$ \Psi(N)=N^2(c_1\log N+c_0)+O(N^{3/2+\varepsilon}) $$will be presented. This formula can be generalized for the case of Gauss-Kuz'min statistics and gives a result about quadratic irrationals. In particular it implies that continued fraction expansions of purely periodic quadratic irrationals have the same statistical properties as continued fraction expansions of almost all real numbers.

#### Zahlentheoretisches Kolloquium

**Title:**$LS$-sequences of points in the unit square

**Speaker:**Maria Rita Iacò (University of Calabria)

**Date:**Freitag, 15.Juni 2012, 15 Uhr

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

In this talk we present $LS$-sequences of points in the unit square. The one-dimensional case has been studied by I. Carbone [1], who proved that, whenever $L\geq S$, the $LS$-sequences of points, denoted by $\{\xi_{LS}^n\}$, have low discrepancy.

We consider the two following extensions to the unit square.[0,3cm]

Definition.} \rm{For each $LS$-sequence of points $\{\xi_{LS}^{n}\}$, the sequence $\{(\xi_{LS}^{n}, \frac{n}{N})\}$, where $n=1,\dots, N$, is called $LS$-sequence of points \`a la van der Corput of order $N$} in the unit square.}[0,3cm]

Definition.} \rm{For each pair of $LS$-sequences of points $\{\xi_{L_1S_1}^{n} \}$ and $\{ \xi_{L_2S_2}^{n}\}$, the sequence $\{(\xi_{L_1S_1}^{n}, \xi_{L_2S_2}^{n})\}$ is called $LS$-sequences of points \`a la Halton} in the unit square.}[0,3cm]

An important result concerning the $LS$-sequence of points \`a la van der Corput is given by the following[0,3cm]

Theorem.} The discrepancy of any $LS$-sequence of points \`a la van der Corput $\{(\xi_{LS}^{n}, \frac{n}{N})\}$ of order $N$ in the unit square coincides with the discrepancy of $\{\xi_{LS}^{n} \}$.[0,3cm]

A consequence of the previous theorem is the following[0,3cm]

Corollary.}

For each $L \ge S$ the sequence of points \`a la van der Corput $\{(\xi_{LS}^{n}, \frac{n}{N})\}$ of order $N$ has low discrepancy.[0,3cm]

It is an open question how do the Halton-type sequences behave. We present several graphical examples which indicate that the situation varies very much. Some sequences seem to be uniformly distributed, while other show an unexpected bad behavior.

\begin{thebibliography}{}

\bibitem {Carbone} I. Carbone, Discrepancy of $LS$ sequences of

partitions and points, {\it Ann. Mat. Pura Appl.} Published online: June 11, 2011, DOI: 10.1007/s10231-011-0208.

\bibitem{Carbone2} I. Carbone, A van der Corput-type algorithm for $LS$-sequences of points, {\it Preprint} (2012)

\end{thebibliography}

#### Zahlentheoretisches Kolloquium

**Title:**$LS$-sequences of points in the unit interval

**Speaker:**Ingrid Carbone (University of Calabria)

**Date:**Freitag, 15.Juni 2012, 14:15 Uhr

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

In [5] Vol\v{c}i\v{c} generalized Kakutani's splitting procedure ([4]), introducing the concept of $\rho$-refinement of a partition $\pi$ of $[0,1]$. He proved that the sequence of partitions $\{\rho^n \omega\}$ is uniformly distributed. Here $\omega$ is the trivial partition of $[0,1]$, and $\rho^n \omega$ is obtained by subdividing all the intervals of $\rho^{n-1}\omega$ having maximal length homothetically to $\rho$.

Recently in [1] the authors gave necessary and sufficient conditions on both $\pi$ and $\rho$ under which the sequence $\{\rho^n \pi\}$ is u.d..

In [2] it has been introduced and studied a countable class of sequences of $\rho$-refinements, denoted by $\{ \rho_{LS}^n \}$, where $\rho$ is the partition made by $L$ intervals of length $\beta $ and $S$ intervals of length $\beta^2$. Estimates of their discrepancy have been also given, and in particular it has been proved that whenever $L\ge S$, the corresponding $LS$-sequence of partitions has low discrepancy.

In the same article it has been presented an explicit algorithm \'a la van der Corput which associates to each $LS$-sequence of partitions a so called $LS$-sequence of points, denoted by $\{ \xi_{LS}^n \}$. These sequences of points have the best possible discrepancy. Actually, to each low discrepancy $LS$-sequence of partitions it corresponds an $LS$-sequence of points with low discrepancy.

In [3] we present two new algorithms to construct $LS$-sequences of points. One of them uses the $(L+S)$-radix notation of integer numbers, and does not need the concept of $LS$-sequence of partitions.

\begin{thebibliography}{}

\bibitem {A} C. Aistleitner, M. Hofer, Uniform distribution of generalized Kakutani's sequence of partitions, to appear in {\it Ann. Mat. Pura Appl. }

\bibitem {C} I. Carbone, Discrepancy of $LS$ sequences of partitions and points, {\it Ann. Mat. Pura Appl. } (2011) DOI: 10.1007/s10231-011-0208.

\bibitem {C1} I. Carbone, A van der Corput-type algorithm for $LS$-sequences of points, preprint.

\bibitem {K} S. Kakutani, A problem on equidistribution on the unit

interval $[0,1[$, {\it Measure theory

(Proc. Conf., Oberwolfach, 1975)}, pp. 369--375. {\it Lecture Notes in Math.} {\bf 541}, Springer, Berlin, 1976.

\bibitem {V} A. Vol\v{c}i\v{c}, A generalization of Kakutani's splitting procedure. {\it Ann. Mat. Pura Appl.}, Nuova Serie {\bf 190} (2011), no. 1, 45-54.

\end{thebibliography}{}

#### Zahlentheoretisches Kolloquium

**Title:**Unique Path Partitions: Characterization and Congruences

**Speaker:**Prof. Dr. James Sellers (Pennsylvania State University)

**Date:**Donnerstag, 14.6.2012, 10:00 s.t.

**Room:**Seminarraum A206, Steyrergasse 30, 2.Stock, Geodäsie

**Abstract:**

Abstract: In this talk, we will describe unique path partitions (whose motivation comes from representation theory of the symmetric group). Once this introduction is complete, we will discuss an explicit characterization of the unique path partitions of $n$ (or up-partitions for short) in terms of partitions we call strongly decreasing (and which are closely related to the non-squashing partitions of Sloane and Sellers). We then discuss numerous connections between up-partitions and certain types of binary partitions. We will close with an analysis of various arithmetic properties of $u(n)$, the number of unique path partitions of $n$. This is joint work with Christine Bessenrodt and Jorn Olsson.

#### Strukturtheorie-Seminar

**Title:**Presentations associated with group actions on sets

**Speaker:**Prof. Thomas Müller (Queen Mary, University of London)

**Date:**Mittwoch, 13. Juni 2012, 16:30

**Room:**Seminarraum C208, Steyrergasse 30, 3. Stock

**Abstract:**

I shall describe a local-global principle which allows one to determine a presentation for a group from its action on a set. After mentioning a number of applications, we shall consider one of them (a new and computer-free approach to the Mathieu groups) in more detail. The talk concludes with a brief discussion of

some rather general ideas related to our method.

#### Strukturtheorie-Seminar

**Title:**Random walks on infinite graphs and groups, Dirichlet harmonic functions, and the Poisson boundary

**Speaker:**Georgakopoulos Agelos (TU Graz)

**Date:**2012-06-12 12:15

**Room:**SR C307

**Abstract:**

The Poisson boundary is well-known for representing the space of bounded harmonic functions on a graph (but also on continuous spaces). I will show a further use of the Poisson boundary: it can be used to analyse the space of (not necessarily bounded) harmonic functions of finite Dirichlet energy. The talk will be accessible to the non-expert. Joint work with V. Kaimanovich.

**Title:**Miniworkshop ``Probabilistic Combinatorics, Random Graphs, and Graph Theory''

**Speaker:**()

**Date:**12.6.2012

**Room:**

**Abstract:**

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

Schedule and Place

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

10:00 – 10:50, AE01, Anna Huber, Durham University

“Randomized Rumor Spreading”

11:00 – 11:50, AE01, Kolja Knauer, TU Berlin

“Three ways to cover a graph”

14:10 – 15:00, C208, Philipp Sprüssel, University of Haifa

“Independent systems of representatives”

15:10 – 16:00, C208, Oliver Cooley, TU München

“A hypergraph analogue of the Erdös-Gallai Theorem via a

simplified hypergraph regularity lemma”

18:30 – 19:20, C209, Dieter Mitsche, Ryerson University, Toronto (Webkonferenz)

“A new upper bound for 3-SAT”

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

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

Titles and Abstracts

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

Speaker: Anna Huber, Durham University

Title: Randomized Rumor Spreading

Abstract:

Randomized rumor spreading is a protocol for disseminating information

on graphs.

The classical version of it has been introduced and first investigated

by Frieze and Grimmett on the complete graph (1985). To start with, one

vertex of a finite, undirected, connected graph has some piece of

information (``rumor''). In each round, every vertex that knows the

rumor informs a neighbor chosen uniformly at random. As a result, the

neighbor vertex now also knows the rumor and begins to inform its

neighbors in the next round.

Frieze and Grimmett showed that on the complete graph, the time needed

to inform all $n$ vertices is within $(1 \pm o(1)) (\log_2 n + \ln n)$

with probability $1 - o(1)$.

I will talk about the performance and robustness of this protocol on

random graphs $G_{n,p}$, and show that the same bounds as for the

complete graph are achieved, as long as $p \geq \frac{\alpha (n) \ln

n}{n}$ for any function $\alpha$ that tends to infinity as $n$ grows.

I will also consider a quasirandom version of the rumor spreading

protocol, proposed by Doerr, Friedrich, and Sauerwald (2008). The basic

setup is the same as in the randomized rumor spreading model, where in

each round every informed vertex contacts a neighbor. But in this model

each vertex has a fixed, cyclic list of its neighbors which dictates the

order in which the vertex contacts them. The first neighbor to be

contacted is determined by choosing a starting position in this cyclic

list at random, independently of the choices of the other vertices. From

that point onwards, in each round the vertex contacts the next vertex on

its list.

I will present the evolution of the quasirandom rumor spreading

protocol and show that, on the complete graph, its performance and

robustness match performance and robustness of the randomized rumor

spreading protocol.

This is joint work with Benjamin Doerr, Spyros Angelopoulos, Nikolaos

Fountoulakis, Ariel Levavi, and Konstantinos Panagiotou.

---------

Speaker: Kolja Knauer, TU Berlin

Title: Three ways to cover a graph

Abstract:

We consider the problem of covering a host graph G with several graphs from a fixed template class T. The classical covering number of G with respect to T is the minimum number of template graphs needed to cover the edges of G. Parameters that arise this way are for example thickness, track-number and all kinds of arboricities.

We introduce two new covering parameters: the local and the folded covering number. As in the global covering number each measures how far G is from the template class in a different way. The folded covering number has been investigated thoroughly for some template classes, e.g., interval graphs and planar graphs, yielding interval and splitting number, respectively. The local covering number was given only little attention.

The three covering numbers presented not only unify the notion in the literature, they as well seem interesting in their own right, e.g., provide new approaches to attack or support classical open problems.

We provide new bounds on some covering numbers w.r.t. several template classes. The classical graph parameters turning up this way are interval-number, track-number, and linear-, star-, and caterpillar arboricity. As host graphs we consider graphs of bounded degeneracy, bounded degree, or bounded tree-width, as well as, outerplanar, planar bipartite and planar graphs. We also discuss some algorithmical questions.

This is joint-work with Torsten Ueckerdt.

---------

Speaker: Philipp Sprüssel, University of Haifa

Title: Independent systems of representatives

Abstract:

Hall's theorem provides a necessary and sufficient condition for the

existence of an injective choice function for a given collection of sets. In a more general setting, some structure is given on the union of these sets and the requirement is added that the range of the choice function belongs to this structure. For example, that the range is independent in some given matroid (this is the setting of Rado's theorem) or independent in some given graph. The elements chosen are then called an "independent system of representatives" (ISR). Many problems can be formulated in this setting for example coloring of graphs, or list coloring. ISR problems are typically NP-hard, so no necessary and sufficient condition is expected to be found for their existence, but some topological and algebraic tools have been developed that provide sufficient conditions. The talk provides an introduction to ISRs as well as presents some of the most recent results.

---------

Speaker: Oliver Cooley, TU München

Title: A hypergraph analogue of the Erdös-Gallai Theorem via a

simplified hypergraph regularity lemma

Abstract:

Erdös and Gallai determined the number of edges required in an

n-vertex graph to guarantee the existence of a path or cycle of length l. We

introduce a hypergraph analogue: We give an upper bound on the number of

edges required in an n-vertex, k-uniform hypergraph to guarantee the

existence of a tight path or cycle of length l. Our bound is asymptotically

best possible up to lower order terms. The proof utilises a new, simplified

form of the notoriously difficult strong hypergraph regularity lemma. In

this talk I will briefly describe the strong hypergraph regularity lemma and

sketch how we derive our simplified version from it using probabilistic

methods.

Based on joint work with Peter Allen, Julia Böttcher and Richard Mycroft.

---------

Speaker: Dieter Mitsche, Ryerson University, Toronto

Title: A new upper bound for 3-SAT

Abstract:

We present a new upper bound for randomly chosen 3-CNF-formulae. In particular we show that a random formula over n variables with clauses-to-variables ratio of at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was 4.506. The first such bound, independently discovered by many groups of researchers since 1983, was 5.19. Several decreasing values between 5.19 and 4.506 were published in the years between. Whereas the improvement is small, our focus is on the methods used. The probabilistic methods we use for the proof are, we believe, of independent interest.

Joint work with J. Diaz, L. Kirousis and X. Perez-Gimenez.

#### Strukturtheorie-Seminar

**Title:**Matrix integral for maps and graphs on surfaces

**Speaker:**Mihyun Kang (TU Graz)

**Date:**13:15 am 5.Juni

**Room:**SR C307

**Abstract:**

Brezin, Itzykson, Parisi, and Zuber showed in [Planar diagrams, Commun. Math. Phys. 59 (1978), 35–51.] that the Gaussian matrix integral of the products of the trace of powers of Hermitian matrices has a useful pictorial interpretation as the number of maps with given degree sequence, sorted by their Euler characteristics (these maps are the Feynman diagrams for the matrix integral). Loebl and I showed in [Advances in Mathematics 221 (2009), 1703-1724] that the number of graphs on surfaces can also be formulated as the Gaussian matrix integral of an ice-type partition function. In this talk I will give a gentle introduction to matrix integral techniques for maps and graphs on surfaces.

#### Vortrag im Seminar Diskrete Mathematik und Optimierung

**Title:**The connection between 2-balanced flows, equal flows and generalized flows

**Speaker:**Michael Moßhammer (Institut für Optimierung und Diskrete Mathematik, TU Graz)

**Date:**5.6. 2012, 14:30

**Room:**Seminarraum C208, Steyrergasse 30, 2. Stock

**Abstract:**

In location theory the 2-balanced flow problem is used to test whether a

given point is an optimal solution of the 1-median problem in the Chebyshev

space.

In fact one has to find a maximum flow with the additional constraint that

the flow on pairs of edges entering the sink has to be the same. This is a

special case of the equal flow problem for which there is still no

combinatorial algorithm known. In this talk, we show that the 2-balanced

flow problem can be solved by a single maximum flow computation.

Furthermore, we discuss the case where the flow on the edges entering the

sink has to satisfy certain proportional constraints. We show how this

generalization of the 2-balanced flow problem can be transformed to a

so-called generalized flow problem, where flow is not conserved on every

arc, i.e., it is allowed that flow leaks as it is sent through the network.

(Joint work with Johannes Hatzl)

#### Zahlentheoretisches Kolloquium

**Title:**New Liouville -type theorems for equations with rescaling

**Speaker:**Prof. Dr. Gregory Derfel (Ben-Gurion University, Israel)

**Date:**Montag, 4. Juni 2012, 15:15 Uhr

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

Joint work with L. Bogachev (University of Leeds), S. Molchanov (University of North Carolina-Charlotte) and J. Ockendon (University of Oxford).

We study the ``archetypical`` functional -integral equation

$y(x)=E[y(\alpha(x-\beta))]$,

where $E(.)$ denotes the expectation with respect to random rescaling coefficients $\alpha$

and $\beta$. Important examples include

(i) functional equation: $y(x)=\sum_{j=1}^\ell p_j y(\alpha_j x + \beta_j)$

(ii) the pantograph equation: $y'(x)+y(x)=\sum_{j=1}^\ell p_j y(\alpha_j x)$,

both under the balance condition: $\sum_{j=1}^\ell p_j=1,\ \ \quad p_j \ge 0$.

Solutions of the archetypical equation can be interpreted as harmonic functions of an

associated Markov chain $X_n$ with i.i.d. jumps of the form $x\longrightarrow\alpha(x-\beta)$.

The problem of characterization of bounded continuous harmonic functions $y=f(x)$

under the assumption $K:=E(\ln\alpha)\neq 0$ was solved by G. D. in

1989. Namely,

if $K\le 0$ then the equation does not have nontrivial (i.e.,

nonconstant) bounded solutions, while if $K>0$ then such a solution

exists.

Our main result is a Liouville -type theorem for the critical case i.e. $K=0$:

if $K=0$, and $f$ is uniformly continuous on $R$, then $f(x)\equiv const $.

The result in the critical case settles a long-standing problem.

The proofs exploit martingale techniques applied to the (bounded) martingale $f(X_n)$.

Furthermore, we show that the uniform continuity condition is garanteed under a mild regularity

assumption on the distributional density $p_{a}(b)$ of the random shift $\beta$ conditioned on

$ {\alpha=a} $: e.g. this condition is automatically satisfied for the pantograph case (ii).

#### Strukturtheorie-Seminar

**Title:**Consistent maximal displacements for branching Brownian motion

**Speaker:**Matthew Roberts (McGill University)

**Date:**30. Mai um 16:00

**Room:**SR C208

**Abstract:**

There has been much recent progress on understanding the system of particles near the frontier of branching Brownian motion, which is a model sharing universality properties with several processes from statistical physics. We consider the question: how close can particles stay to the critical line $\sqrt{2}t$?

**Title:**Doctoral School Seminar

**Speaker:**()

**Date:**25.5.2012, 10:30-13:00

**Room:**Seminarraum 2, Inst. f. Geometrie, Kopernikusgasse 24

**Abstract:**

10:30 Fabrizio Barroero:

O-minimal structures and applications to number theory

11:00 Martin Holler

Artifact-free decompression of transform-coded multi-channel images with TGV

11:30 Break (coffee and refreshments)

12:00 Andreas Kucher:

Algorithms for CFD Calculations on Many–Core Systems

12:30 Daniel Krenn:

Analysis of Non-adjacent Forms in Lattices

#### Strukturtheorie-Seminar

**Title:**On the $K$-theory of crossed products by semimultiplicative sets

**Speaker:**Dr. Bernhard Burgstaller (Salzburg)

**Date:**25.5.2012, 14:15

**Room:**SR C307, Steyrergasse 30, 3. Stock

**Abstract:**

$C^*$-algebras are self-adjoint closed subalgebras of the algebra $B(H)$ of bounded linear operators on a Hilbert space $H$.

Topological $K$-theory is a useful tool in understanding the structure of these algebras.

$K$-theory, a homology theory, gives information of the algebra which has to do with homotopy and

has a touch similar to the one of algebraic topology.

There are some constructions with $C^*$-algebras with astonishing insights.

For instance, the $K$-theory associated to certain $C^*$-algebras (Cuntz-algebras)

reveal invariants of Bowen and Franks for certain dynamical systems.

A bivariant generalization of $K$-theory, the $KK$-theory by Kasparov,

was successfully applied by Kasparov to attack the Novikov conjecture

from differential geometry and verify it in special cases.

The Atyiah--Singer index theorem can well be understood as a map in

$KK$-theory.

In recent years, Baum, Connes and Higson formulated their Baum--Connes conjecture.

It claims that for a locally compact group there exists an isomorphism between the group equivariant $K$-homolgy

and the $K$-theory of the $C^*$-algebra generated by the group.

\par

A semimultiplicative set is

a set with a partially defined multiplication, e.g., groups, groupoids,

semigroups and small categories.

Certain $C^*$-algebras can be realized as

a $C^*$-algebra generated by a semimultiplicative set, or more generally, as crossed products

by semimultiplicative sets.

Motivated by these examples, and

in an attempt to understand the $K$-theory of these crossed products, I started

to extend the Baum--Connes program to semimultiplicative sets.

So far I have extended Kasparov's group equivariant $KK$-theory

to semimultiplicative set equivariant $KK$-theory

and I was able to copy some of the techniques used

in Baum--Connes theory.

But for inverse semigroups I could show the existence of a Baum--Connes map

and that it is an isomorphism in some cases, because I simply have translated inverse semigroup equivariant $KK$-theory

to groupoid equivariant $KK$-theory, and used the known theorems there.

In particular, for a finite inverse semigroup I could show a particular nice form of a Baum--Connes isomorphism,

a result which is already known as Green--Julg isomorphism for compact groups.

#### Seminar Angewandte Analysis und Numerische Mathematik

**Title:**Approximation Vertex Conditions by Geometry

**Speaker:**Dr. Olaf Post (Cardiff University)

**Date:**23.5.2012, 16:30 Uhr

**Room:**C208, Steyrergasse 30

**Abstract:**

Our aim is to approximate a class of vertex conditions for a Laplacian on a metric graph by Laplacians on a family of manifolds shrinking to the metric graph. We characterise the class of vertex conditions in terms of stochastic properties of the semi-group generated by the Laplacian.

#### Conference

**Title:**Statistical Models for Financial Data III

**Speaker:**()

**Date:**May 23-26, 2012

**Room:**BE01

**Abstract:**

#### Strukturtheorie-Seminar

**Title:**The normal law, matchings and walks in Young's lattice

**Speaker:**Franz Lehner (TU Graz)

**Date:**Dienstag, 22.5.2012, 12 Uhr c.t.

**Room:**SR C307, Steyrergasse 30, 3. Stock

**Abstract:**

It is known that the sequence so-called free cumulants of the normal law is positive definite. So far there is no combinatorial proof of this fact, although there are many bijections to popular combinatorial objects like matchings, trees etc. We survey some of these bijections.

#### Vortrag

**Title:**The decimation process in random k-SAT

**Speaker:**Pachon Angelica (TU Graz)

**Date:**am 15.05.2012 um 11:15

**Room:**SR C307

**Abstract:**

(jointly with Amin Coja-Oghlan) Let $\Phi$ be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-rigorous statistical mechanics ideas have inspired a message passing algorithm called 'Belief propagation guided decimation' for finding satisfying assignments of $\Phi$. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the decimation process. In this paper we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm.

#### Zahlentheoretisches Kolloquium

**Title:**Patterns in rational base number systems

**Speaker:**Prof. Dr. Wolfgang Steiner (CNRS, LIAFA, Univ. Paris 7)

**Date:**Montag, 14.Mai 2012, 17:00 Uhr, c.t.

**Room:**Seminarraum A206, Steyrergasse 30, 2.Stock, Geodäsie

**Abstract:**

Abstract:

Akiyama, Frougny, and Sakarovitch recently introduced number systems with a rational number as base. They established relations to Mahler's 3/2-problem as well as the Josephus problem. We show that the patterns of digits in the expansions of positive integers are uniformly distributed in these number systems. We study the sum-of-digits function of number systems with rational base p/q and use expansions w.r.t. this base to construct normal numbers in base p in the spirit of Champernowne. In the proofs we use self-affine tiles that are defined in certain subrings of the adele ring. (joint work with Johannes Morgenbesser and Jörg Thuswaldner)

#### Zahlentheoretisches Kolloquium

**Title:**Metric properties of systems of numeration

**Speaker:**Doz. Dr. Guy Barat (Marseille/TU Graz)

**Date:**Montag, 14.Mai 2012, 16:00 Uhr, c.t.

**Room:**Seminarraum A206, Steyrergasse 30, 2.Stock, Geodäsie

**Abstract:**

In this joint work with Peter Grabner, we revisit the notion of odometer

introduced in 1995 in a paper of Grabner, Liardet and Tichy. An odometer is a dynamical system extending the addition of 1 to a suitable compatification of the set of non-negative rational integers related to their representation (system of numeration). Using combinatorics on words and basic results from functional analysis, we can prove the existence of invariant measures on the odometer and give sufficient conditions for their unicity.

#### Strukturtheorie-Seminar

**Title:**An introduction to zigzag and other products of graphs

**Speaker:**Dr. Alfredo Donno (Università di Roma La Sapienza)

**Date:**Dioenstag, 8.5.2012, 12:00 Uhr (s.t.)

**Room:**SR C307, Steyrergasse 30, 3. Stock

**Abstract:**

In this talk I want to present an interesting product of graphs, which is called the zigzag product, introduced by Reingold, Vadhan and Wigderson (Annals of Mathematics, 2002). This simple construction allows to produce infinite families of constant-degree expanders of arbitrary size. On the other hand, the zigzag product is also related to Group Theory via the notions of semidirect product and Cayley graphs.

I also would like to hint at some other conjectures and ideas concerning connections with other products of graphs and groups, like the wreath products, the generalized wreath products, or the family of graph products introduced by Imrich and Izbicki in 1975, as well as with the well-known Lamplighter Markov chain.

#### Zahlentheoretisches Kolloquium

**Title:**Values of quadratic polynomials represented by norms

**Speaker:**Prof. Dr. Ulrich Derenthal (Ludwig-Maximilians-Universität München)

**Date:**Freitag, 4. Mai 2012, 14:15 Uhr

**Room:**Seminarraum C 208, 2. Stock, Steyrergasse 30, TU Graz

**Abstract:**

Abstract: Let $K/k$ be an extension of number fields. When can values of

a quadratic polynomial $P(t)$ over $k$ be represented by norms of elements

of $K$? To answer this question, we will discuss the Hasse principle and

weak approximation for the affine variety defined by

$P(t)=\mathrm{Norm}_{K/k}(x)$, in particular in the case $[K:k]=4.$ This is joint

work with A. Smeets and D. Wei, extending recent work of T. D.

Browning and D. R. Heath-Brown.

#### Strukturtheorie-Seminar

**Title:**The duality between jump processes on ultrametric spaces and random walks on trees

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

**Date:**Mittwoch, 25. April, 16:00 s.t.

**Room:**Seminarraum C208, Steyrergasse 30, 3. Stock

**Abstract:**

The purpose of this talk is to clarify the duality between a natural class of jump processes on compact ultrametric spaces - studied in current work of Bendikov, Girgor'yan and Pittet -- and nearest neighbour random walks on trees.

Processes of this type have appeared in recent work of Kigami. Every compact ultrametric space arises as the boundary of a locally finite tree. The dualty arises via the Dirichlet forms: one on the tree associated with a random walk and the other on the boundary of the tree, which is given in terms of the Naim kernel. In the talk, it will be explained that up to a linear time change by a unique constant, there is a one-to-one correspondence between the above processes and Dirichlet regular random walks.

Bitte die Kurzfristigkeit der Ankündigung zu entschuldigen !