Discrete Mathematics 2010-2022

Jigsaw percolation, introduced by Brummit, Chatterjee, Dey and Sivakoff, may be viewed as a measure of whether two graphs on the same vertex set are ``jointly connected'': Given two such graphs, we ``merge'' two vertices if they are connected in both graphs, and the new vertex inherits all of the neighbours of the old vertices in both graphs. We continue until no more vertices can be merged and say the process percolates} if it ends with a single vertex.

Bollob\'as and Riordan proved that if the two graphs are independent binomial random graphs $G(n,p_1)$ and $G(n,p_2)$, then there is a threshold for percolation based on the product $p_1p_2$ of the two edge probabilities. However, they only determined the location of this threshold up to a constant factor.

In this talk we will present work in progress towards finding the exact threshold. This is based on joint work with Tobias Kapetanopoulos, Tam\'as Makai and Kathrin Skubch.

This talk will be a gentle introduction to the field of enumerative combinatorics.

Generating functions are a standard tool in enumerative combinatorics. In order to count the objects in a given class of combinatorial structures, the numbers of objects of different sizes are represented in a formal power series. Constructive decompositions of the objects in the class correspond to certain functional operations for the power series. Tools for analysing such operations allow to determine the exact or asymptotic numbers of objects in the class. However, if one wants to count objects up to some type of isomorphism, this approach usually fails.

In this talk, we present a different formal representation of combinatorial classes that takes isomorphisms into account: cycle index sums. These formal sums represent not only the objects in a given class, but also the orbits of their automorphisms, which makes it possible to represent constructive decompositions by functional operations that depend on the orbit.

I will describe the limit moments of a random matrix of Wishart type $BB^*$, where $B$ is a product of (classically) independent rectangular random matrices, using combinatorics related to matricially free probability. Those moments will be expressed in terms of noncrossing partitions with even blocks related to certain words, and then using $R$-, $S$- and $T$-transforms well known in free probability we give an explicit formula for those moments, connecting them with the multivariate Fuss-Narayana polynomials. At the end I'll present some partial results without the assumption of independence of random matrices. The results are joint work with R. Lenczewski.

Bootstrap percolation on a graph, with infection threshold a positive integer $r$, is an infection process which starts out from a set of initially infected vertices and in each further step every vertex with at least $r$ infected neighbours becomes infected. The process stops once no further vertices can become infected.

We consider bootstrap percolation on the binomial random graph $G(n,p)$, when the set of initially infected vertices has size $a$, which was investigated by among others by Janson, \L uczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of infected vertices at the end of the process.

This is joint work with Mihyun Kang.

Abstract: Let A be an abelian variety over a number field K. We are
interested in its group of K-rational points A(K), which is finitely
generated by the Mordell-Weil Theorem. We show how to provide an explicit
upper bound on the rank of A(K) in terms of the height of A and the
discriminant of K. The proof uses a new inequality between the height and
bad reduction primes, which is obtained by combining a jacobian argument,
a Bertini Theorem and the existence of unramified towers over certain
quadratic number fields.

Abstract: We explore in depth the number theoretic and statistical properties of certain sets of numbers arising from their Cantor series expansions. As a direct consequence of our main theorem we deduce numerous new results as well as strengthen known ones.

For integers $g,m\ge 0$ and $n>0$, let $S^g_{n,m}$ denote the graph taken uniformly at random from the set of all graphs on $\{1,2, \ldots , n\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S^g_{n,m}$, finding that there is often different asymptotic behaviour depending on the ratio $m/n$.


This is joint work with Mihyun Kang and Philipp Sprüssel.

Abstract:
Stochastische Steuerung für Versicherungen ist mittlerweile ein lebendiges Teilgebiet der
Mathematik, es hat sich nach anfänglichen Versuchen, Methoden aus dem Finance zu adaptieren,
etwas eigenständiger weiterentwickelt. Dazu gehören Methoden zur Lösung von Integro-Differentialgleichungen,
von Nebenbedingungen, von Modifizierungen der Argumente für Viskositätslösungen und nicht-stationäre Ansätze
für Mischungsmodelle. Schwerpunkt liegt in der numerischen Umsetzung und der Interpretation der numerischen Resultate.

We propose exact solution approaches for two different
generalization of the 0-1 Knapsack Problem, that is the
0-1 Knapsack Problem with Setups and the 0-1 Collapsing
Knapsack Problem. In the first problem, the items belong
to disjoint families (or classes) and they can be picked
only if the corresponding family is activated. The
selection of a class involves setup costs and resource
consumptions thus affecting both the objective function
and the capacity constraint. In the 0-1 Collapsing
Knapsack Problem, the capacity of the knapsack is not a
scalar but a non-increasing function of the number of
items included, namely it is inversely related to the
number of items placed inside the knapsack. The solution
approaches we propose rely on an effective exploration of
a specific set of variables that leads to solve standard
knapsack problems and on dynamic programming. For the
Knapsack Problem with Setups, a series of approximation
results is also provided.

\vspace{1cm}

14:00: Laia Amorós (University of Luxembourg)
From modular curves to Shimura curves: a p-adic
approach

15:00: Tetiana Stepaniuk (Lesya Ukrainka Eastern European National University)
Approximative characteristics of
classes of convolutions

We develop the asymptotic formulas for correlations
\[
\sum_{n\le x}f_1(P_1(n))f_2(P_2(n))\cdot \dots \cdot f_m(P_m(n))\] where $f_1,\dots,f_m$ are bounded ``pretentious'' multiplicative functions, under certain natural hypotheses. We then deduce several desirable consequences: first, we characterize all multiplicative functions $f:\mathbb{N}\to\{-1,+1\}$ with bounded partial sums. This answers a question of Erd\H{o}s from $1957$ in the form conjectured by Tao. Second, we show that if the average of the first divided difference of multiplicative function is zero, then either $f(n)=n^s$ for $\operatorname{Re}(s)<1$ or $|f(n)|$ is small on average. This settles an old conjecture of K\'atai. If time permits, we discuss multidimensional analog of the results above and its application to the study of Gowers norms of multiplicative functions. Finally, we apply these techniques to study sign patterns of $(f(n),f(n+1),f(n+2))$ and $(f(n),f(n+1),f(n+2),f(n+3))$ where $f:\mathbb{N}\to \{-1,1\}$ is a given multiplicative function.

Nach einer kurzen Wiederholung elementarer Eigenschaften von Martingalen betrachten wir das 'Optional Stopping Theorem' von Doob. Nach dessen Herleitung wollen wir dieses Resultat auf das Problem {\it Wie lange benötigt ein Affe in Erwartung um auf der Schreibmaschine ABRACADABRA zu tippen?} anwenden.

Phase retrieval refers to restoring a signal from intensity measurements
only and is important in several application areas ranging from X-ray crystallography and microscopy to audio processing and deep learning. Due to the substantial amount of missing information, phase retrieval problems are extremely challenging to solve numerically.

We shed some light on the origin of these difficulties and we propose a novel paradigm of weaker stability which actually achieves stable phase retrieval in several applications.

This is joint work with R. Al-Aifari (ETH Zurich), I. Daubechies (Duke University) and R. Yin (Duke University)

Bitte geänderte Beginnzeit beachten (14:00 puenktlich) - Please note the changed starting time (14:00).

The Turan function ex$(n,F)$ of a graph $F$ is the maximum number of edges in an $F$-free graph with $n$ vertices. The results of Turan and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine the minimum number of copies of $F$ that a graph with n vertices and ex$(n,F)+q$ edges can have. In general, this problem seems to be very difficult and is wide open.

I will present joint results with Zed Yilma, where we concentrate on the case when $q=o(n^2)$ and $F$ is colour-critical (that is, the removal of some edge from $F$ decreases its chromatic number).

The classic analysis of the probability that the Galton-Watson tree is infinite gives an equation with two solutions. What about other properties. For first order properties we show that the equation system has a unique solution. When conditioning on the tree being infinite the probabilities of first order properties are particularly nice. More generally we consider properties defined by tree automata. These are associated with Monadic Second Order Logic. There is then a natural equation system. Sometimes the system has rogue solutions, meaning solutions with no interpretation. This area combines structural combinatorics, probabilistic combinatorics and logic. (Joint work with Moumanti Podder.)

The hexagonal lattice gives the highest density circle packing among all lattices in the plane.
In this talk I first recall the basic notions about lattices in the plane, before I construct a sequence of lattices with integer bases that approximate the hexagonal lattice. The construction uses elementary number theory and is based on particular palindromic continued fraction expansions. As an application I obtain lattices modulo N with longest possible shortest distances.

14:00 {\bf H. Edelsbrunner} (ISTA): {\bf Distances and divergences in
topological data analysis}.
Given a finite set in a metric space, the topological
analysis assesses its multi-scale connectivity quantified in terms
of a $1$-parameter family of homology groups. Going beyond metrics,
we show that the basic tools of topological data analysis also
apply when we measure dissimilarity with Bregman divergences.
A particularly interesting case is the relative entropy whose
infinitesimal version is known as the Fisher information metric.
It relates to the Euclidean metric on the sphere and, perhaps
surprisingly, the discrete Morse properties of random data
behaves the same as in Euclidean space.

{\bf Coffee Break}

15:30 {\bf Raman Sanyal} (Goethe-Univ.\ Frankfurt): {\bf The geometry of double posets}, In 1984 Stanley showed that partially ordered sets (posets)
can be studied from the perspective of geometry. His order- and chain
polytopes express combinatorial properties of posets as
geometric quantities, furnishing a number of deep results
in both combinatorics and geometry.
In 2011, Malvenuto and Reutenauer introduced double posets (finite
sets equipped with two partial order relations). This notion
underlies many constructions in algebraic combinatorics such as P-partitions,
Littlewood-Richardson rules, permutation statistics.
In this talk, I will explain how double posets can be studied from a geometric
point of view, highlighting connections to
centrally-symmetric polytopes (weak Hanner polytopes), combinatorial
optimization (anti-blocking polytopes), valuations on distributive lattices,
and generalized Hibi (semigroup) rings. This is joint work with T.\ Chappell
and T.\ Fried.



16:20 {\bf Wöden Kusner} (TU Graz): {\bf Critical packings, rigidity, and the radius function}.
There are a number of classical problems in geometric optimization that ask
for the ``best'' configuration of points with respect to some function. We are
interested in the relationships between various notions of criticality for
such functions on configuration spaces, in particular the injectivity or
packing radius.  This is not a Morse function, but it has been observed to
be Morse-like, in that the topological notion of regularity can be defined
in an analogous way.  Furthermore, there is a geometric interpretation from
rigidity theory that characterizes configurations as critical by the
existence of a strut measure.

The Nerve Theorem is an implicit tool in most application of topological data analysis relating the topological type of a suitably nice space with a combinatorial description of the space, namely, the nerve of a cover of that space. It is required that it is a good cover, that each element and intersection is contractible or at least acyclic. In this talk, I will describe a weaker condition we call an epsilon-acyclic cover. It encodes the idea that if a cover is almost a good cover, the persistent homology of a filtration computed on the nerve is a good approximation of the persistent homology of a filtration on the underlying space. The main application of this result is to reduce the computational burden for computing persistence by allowing the use of coarser representations of the space (e.g. smaller simplicial complexes). I will also describe how to obtain explicit error bounds from local computations.

I will discuss the efficient computation of the persistence barcode of a Vietoris--Rips filtration given a finite metric space. The implementation in the developed C++ code “Ripser” focuses on memory and time efficiency, where the code outperforms existing software by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency.

Motivated by real-time logistics, I will present a deterministic algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations. The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R. The algorithm that I present is based on a variant of the offline primal-dual method where the constraint for every edge is relaxed by a fixed multiplicative factor. Using the fact that the costs between locations satisfy triangle inequality, I will show that this deterministic algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models.

Bio: Dr. Sharath Raghvendra is an Assistant Professor in the Department of Computer Science at Virginia Tech. Before joining Virginia Tech, he spent two years as a postdoctoral scholar at Stanford University. Dr. Raghvendra received his Ph.D from Duke University in 2012 where he won the Best Doctoral Dissertation Award. He is also the recipient of NSF CRII Award in 2014. His research interests span design of algorithms for problems in computational geometry and graph theory.

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

Program
======

10:00-10:30: Get together and coffee (Steyrergasse 30, 2nd floor)

10:30-10:40: Opening


10:40-11:25: Gerhard J. Woeginger (Eindhoven University of Technology)
LP relaxations for two scheduling problems

11:30-12:15: Ante Custic (Simon Fraser University)
The Bilinear Assignment Problem: Complexity, polynomially solvable special
cases and heuristics


12:15-14:15: Lunch break


14:15 -15:00:  Günter Rote (FU Berlin)
Loopless Gray Code Enumeration and the Tower of Bucharest

15:05-15:50:  Vladimir Deineko (Warwick Business School)
On solvable cases of the 2-period-balanced-TSP and benchmark test problems


15:50-16:05: Coffee break


16:05-16:50: Ulrich Pferschy (University of Graz)
The Quadratic TSP (without special cases...)


16:50-17:00: Closing


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

\begin{coauthors}
Coauthors: A. Dossavi-Yovo, B. Faye, B. Kafle and Alain Togb\'e
\end{coauthors}

Let $d\geq 2$ be an integer which is not a square. Let $(X_n,Y_n)_{n\ge 1}$ be the sequence of positive integer solutions $(X,Y)$ of the Pell equation $X^2-dY^2=c$, where $c\in \{\pm 1,\pm 4\}$. We then show that there is at most one
$n$ such that $X_n$ is a rep-digit in base $10$, with a few exceptions in $d$. The same result holds if we impose that $X_n$ is a rep-digit in any fixed integer base $b\ge 2$ or a member of the Fibonacci sequence. The proofs use linear forms in logarithms of algebraic numbers.