Seminar on Combinatorics

主講者: 1.沈俊嚴教授 (國立中央大學) Dr. Michael Wallner (中研院統計所)
講題: 1.A new bound for Balog's conjecture on the size of the set AA+A 2.Limit laws for lattice paths with catastrophes
時間: 2017-07-05 (Wed.)  14:00 -
地點: 數學所 722 研討室 (台大院區)
Abstract: 1.The sum-product conjecture of Erdos-Szemeredi asserts that one of the sum set and product set has size near-quadric growth. Many variants of this conjecture have been well studied. In particular a question posed by Bourgain is to characterize the functions of multiple variables that have expanding property. In this talk, we will discuss our recent advances on making an $\epsilon$ progress for Balog's conjecture which is closely related to a weaker version of Erdos-Szemeredi conjecture.

2.In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths or random walks, it is like having the possibility of jumping from any altitude to zero. Because of this we call them "lattice paths with catastrophes". These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour like classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). In this talk we will quantify some relations between these two types of paths. We give a bijection with some other lattice paths, show a link with a continued fraction expansion, and prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. Our main tools will be the kernel method and asymptotic transfer theorems from analytic combinatorics. With these we solve the enumeration problem and derive several limit laws for parameters like the number of returns to zero or the size of an average catastrophe. We end with some considerations on uniform random generation. This is joint work with Cyril Banderier.

  || Close window ||