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.