Symposium on combinatorics and probability

Abstract. In this lecture, I intend to introduce the basic framework of game theoretic choice problems and combinatorial games. I am also planning to discuss some open problems, particularly the ones that involve probability (mainly discrete). The objective of this lecture is to give students an idea of some research areas in Game Theory.

Abstract. Random walks on networks are a way to model reversible Markov chains. This point of view makes several notions more natural and these notions can be used to get quite powerful results about the probabilities or even rates of escape of a random walk. We shall discuss the Nash–Williams inequality which will eventually help us prove an interesting and somewhat counter-intuitive result about a knight's random walk on a bi-infinite chessboard. We would also survey a few broad classes of techniques which can be helpful to understand not just the probability of escape but even the rate of escape of random walks.

Abstract. We shall discuss a fascinating and fundamental result of probability theory, the Lovász Local Lemma, which roughly says that a set of "bad" events do not occur with positive probability provided the dependence between them is restricted. Thereafter, we shall explore its far-reaching applications in solving various deterministic problems arising in combinatorics, graph theory, and algorithms. Finally, since the LLL is non-constructive by nature, we shall also briefly discuss modern research on this topic that aims at finding efficient algorithms for putting this mighty probabilistic tool in action.

Abstract. In this talk, we will discuss certain special proprieties of polynomials with non-negative coefficients but with only real zeros. We will sketch that for such polynomials with high degree, the asymptotic limits of the coefficients can easily be derived using certain probabilist techniques. We will illustrate with examples of few important combinatorial sequences, namely, (i) Binomial Coefficients: the number of subsets of a set with $n$ objects which are exactly of the size $k$; (ii) Stirling's Number of Ist Kind: the number of permutations of $n$ objects with exactly $k$ cycles; and (iii) Stirling's Number of IInd Kind: the number of partitions of a set with $n$ objects into exactly $k$ parts. We will show that they all have an "universal" asymptotic limit and discuss the the relation with one of the most celebrated result in Probability Theory, namely, the Central Limit Theorem (CLT). In the process, we will outline a very powerful combinatorial technique, known as the Harper's Method.

[The talk will only need basic concepts from probability theory.]

Abstract. A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straight-line segments between these points. There are many interesting results and open problems about geometric graphs that are relevant to well known problems in discrete and computational geometry, such as the halving line problem (Erdős–Lovász–Simmons–Straus), questions on repeated distances and incidences (Erdős, Szemerédi–Trotter), etc. We survey some basic results in geometric graph theory and highlight some open problems whose solution may be within reach.

Abstract. There are several questions in mathematics which are unrelated to probability theory where bringing in ideas from probability theory leads to alternate proofs, which may be shorter or easier to understand, Weierstrass's result on approximating continuous functions on $[0,1]$ by polynomials is one such.

In this talk, we will discuss one such numerical question involving large finite sets where bringing in Markov chains and the related Monte Carlo technique seems to be the only way to approximate the answer. We will also introduce the required background on Markov Chains.

Abstract. Branching random walk is a system of growing particles that starts with one particle. This particle branches into a random number of particles, and each new particle makes a random displacement independently of each other and of the branching mechanism. The same dynamics goes on and gives rise to a branching random walk. This model arises in statistical physics, mathematical biology, ecology, etc. It is important because it has connections to various probabilistic objects. In this overview talk, we shall try to answer the following question: if we run a branching random walk for a very long time and take a snapshot of the particles, how would the system look like? We shall investigate how the tails of the progeny and displacement distributions change the answer to this question.

This talk is based on a series of joint work with Ayan Bhattacharya, Rajat Subhra Hazra, Krishanu Maulik, Zbigniew Palmowski, Souvik Ray and Philippe Soulier.

Abstract. We discuss several results on proper graph coloring and graph choosability by a polynomial method of Alon and Tarsi and its further development.