Discrete Mathematics 2010-2022

The study of the partition function $p(n)$, counting the number of solutions of
the equation $n=a_{1} + \dots + a_{\ell}$ over integers
$1 \leq a_{1} \leq \dots \leq a_{\ell}$, has a long history in combinatorics. In
the present talk we consider the following variant of this question: partitions
in integers of the form
\begin{equation*}
n=\lfloor a_1^\alpha\rfloor+\cdots+\lfloor a_\ell^\alpha\rfloor
\end{equation*}
with $1\leq a_1< \cdots < a_\ell$ and $0 < \alpha < 1$ a fixed real. Using the
saddle point method we show a central limit theorem for the number of summands
in a random partition of that kind.

This is joint work with Gabriel Lipnik and Robert Tichy.

Let $L_{c,n}$ be the length of the longest cycle in a sparse binomial random graph $G_{n,p}$, $p = c/n$, $c>1$. Erd\H{o}s conjectured that if $c>1$ then w.h.p. $L_{c,n}\geq \ell(c)n$ for some strictly positive function on $(1,\infty)$ that is independent of $n$. His conjecture was proved by Ajtai,
Koml\'os and Szemer\'edi and in a slightly weaker form by Fernandez de la Vega. Henceforward there has been a line of research in trying to bound $L_{c,n}$ for $c>1$. In this talk we will discuss how one can identify a set of vertices that spans a longest cycle in $G_{n,p}$ w.h.p for sufficiently large $p$. We will then show that $\frac{L_{c,n}}{n}$ converges to some continuous function $f(c)$ almost surely which can be evaluated within arbitrary accuracy for $c>C_0$ where $C_0$ is a sufficiently large constant. This talk is based on a joint work with Alan Frieze.

Meeting link:
\[
\text{https://tugraz.webex.com/tugraz/j.php?MTID=m40f85343e56ff5051d731ace1bea82e4}
\]

Meeting number: 2731 089 0467

Password: btHRJxCa252