Discrete Mathematics Day 2014: May 16, 2014; 1 pm.

   Karl Franzens University, Lecture Hall HS 11.02, Heinrichstraße 36.

There will be two plenary talks, and four short talks by DK students or associated students. The talks will take place at Karl Franzens University, in lecture hall HS 11.02, with the exception of the talk of Christian Krattenthaler (University of Vienna). His talk will take place at Institut für Musikwissenschaft (Meerscheinschlössl Festsaal), since a piano is needed.

Main speakers

Short talks

  • Ante Ćustić (TU Graz)
  • Christoph Koch (TU Graz)
  • Milton Minervino (MU Leoben)
  • Hannah Vogel (KFU Graz)

Program: PDF File

  • 1315-1325: Opening
  • 1325-1350: Milton Minervino
    Title: Rauzy fractals and tilings
  • 1350-1415: Hannah Vogel
    Asymptotic triangulations, Dehn twists, and coxeter transformations.
  • 1415-1425: Short break
  • 1425-1510: Plenary Talk: Clemens Heuberger
    Digit expansions and Transducer Automata
  • 1510-1540: Coffee break
  • 1540-1605: Ante Ćustić
    On the constant objective value property for combinatorial optimization problems.
  • 1605-1630: Christoph Koch
    Title: The size of the largest component in random hypergraphs.
  • 1700-1800: Christian Krattenthaler
    Meerscheinschlössl Festsaal, Institut für Musikwissenschaft.
    Musik und Mathematik.

Poster of the workshop DK Day 2014.
Folder of the talk Mathematik und Musik.
Program of the DK Day 2014 as a PDF File.

Abstracts:

  • Milton Minervino
    Title: Rauzy fractals and tilings.
    Abstract:

    Rauzy fractals are geometric objects arising in the study of symbolic dynamical systems generated by Pisot substitutions. One of the main dynamical problems in this field is translated geometrically to a tiling problem by Rauzy fractals. We give an overview of this famous open problem and we sketch the main issues when going beyond the main hypotheses.

  • Hannah Vogel
    Title: Asymptotic triangulations, Dehn twists, and coxeter transformations.
    Abstract:

    Asymptotic triangulations can be viewed as limits of triangulations under the action of the mapping class group (cf. BD). In this talk, we construct an alternative method of obtaining asymptotic triangulations using Coxeter transformations. This provides us with an algebraic and combinatorial framework for studying these limits via the associated quivers and root systems.

  • Clemens Heuberger
    Title: Digit expansions and Transducer Automata
    Abstract:

    Motivated by applications in the efficient implementation of elliptic curve cryptosystems, we study digit systems with minimal weight (number of non-zero digits). We emphasise the use of transducer automata as an important tool to design and analyse optimal expansions. In particular, some asymptotic and probabilistic properties can be characterised combinatorially. The use of the computer algebra system Sage to automatically answer some of the arising questions is demonstrated.

  • Ante Ćustić
    Title: On the constant objective value property for combinatorial optimization problems.
    Abstract:

    For a given combinatorial optimization problem we want to characterize the space of all instances for which every feasible solution has the same objective value. In the case of linear combinatorial optimization problems, such instances are in 1:1 correspondence to the notion of admissible transformations, i.e. transformations of the instances that preserve the relative order of objective values of all feasible solutions. Admissible transformations can be used to solve the problem or to find good lower bounds. In this talk we will focus mainly on multidimensional assignment problems. We show that for the axial and for the planar d-dimensional assignment problem the instances with constant objective value property are characterized by sum-decomposable arrays. We give a counterexample to show that this is not the case for more general multidimensional assignment problems. The talk is concluded with comments on results for other types of combinatorial optimization problems.

  • Christoph Koch
    Title: The size of the largest component in random hypergraphs
    Abstract:

    Phase transitions are one of the most central topics of random discrete structures. In this talk we study the phase transition of the largest component (with respect to $j$-tuple connectivity) of the uniform binomial random hypergraph. We determine the asymptotic size of the largest component including the precise constant in the weakly supercritical regime and thereby extend a recent result by Cooley, Kang and Person. Our result is based on a refined branching process approach that was used by Bollobás and Riordan to reprove the corresponding result for the binomial random graph. Furthermore this method provides some insight into the structure of large components in the binomial random hypergraph. This is joint work with Oliver Cooley and Mihyun Kang.

For coffee break, it is required to register by sending an email to discrete@tugraz.at.