Title: Probabilistic Methods in combinatorics (Hypergraph 2-coloring)
Speaker: Rahul Gangopadhyay
Date: April 11, 2019 (Thursday)
Abstract: This talk is a brief survey on the hypergraph 2-coloring problem which is also known as Property-B for a set system. Erdos and Lovasz first proposed this problem for uniform hypergraphs. Lovasz proved that it is NP-complete to decide if an arbitrary hypergraph is 2-colorable. Erdos proved that there exists a $n$-uniform hypergraph with $\Theta((n^2)2^n)$ hyperedges which is not 2-colorable. He used probabilistic methods in the proof. He also conjectured that all the $n$-uniform hypergraphs with $O((n)2^n)$ hyperedges are 2-colorable.This conjecture is not resolved till now. We will discuss three results which prove weaker bounds than Erdos conjectured. All these proofs involve probabilistic methods. Also Erdos result on non-2-colorability is existential in nature. It is still an open problem to create a non-2-colorable $n$-uniform hypergraph with $\Theta((n^2)2^n)$ hyperedges. Gebauer gave the best constructive bound of $\Theta((2^(n^(2/3)))2^n)$ on this quantity. We would also like to discuss this proof. In the end, we will try to show the application of Lovsz's Local Lemma in hypergraph 2-coloring.

Title: Stochastic Nash games under chance constraints
Speaker: Vikas Vikram Singh
Date: March 28, 2019 (Thursday)
Abstract: The strategic games with stochastic payoffs and constraints have been extensively studied in the literature. The case of risk neutral decision makers has been studied by considering the expectation of random payoffs and constraints. We use chance constraint programming to model the risk averse stochastic Nash games. We show the existence of Nash equilibrium for the case of elliptically symmetric distributions. We also consider the case where underlying probability distribution is only known to belong to a distributional uncertainty set. These cases are modelled by considering the worst case situation using distributionally robust approach. We showed the existence of Nash equilibrium for various distributional uncertainty sets. We also discuss some computational approaches to compute the Nash equilibrium for these games.