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

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

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

{\bf Kaffeepause}

{\bf 17:30: Vinko Petricevic} (Univ. of Zagreb)
{ Householder's approximants and continued fraction expansion

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

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

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

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 !