The regularity lemma (due to E. Szemeredi) states that for a given $\epsilon>0$ every graph can be partitioned into $k< M(\epsilon)$ equitable parts {V_1,V_2,..,V_k} such that except for at most $\epsilon k^2$ of these pairs, the rest are $\epsilon$-regular. The proof of the regularity lemma obtains a $k$ which grows as a tower of 2's of height $\Omega(1/\epsilon^5)$. Gowers however showed that this type of tower growth is unavoidable, and simpler proofs were later given by Conlon and Fox. We shall look at another one which is considerably simpler, due to Shapira and Moschovitz.

In 1979, Lovasz gave a beautiful simple *randomized* algorithm to detect if a given bipartite graph has a perfect matching, which involves computing the determinant of the Tutte matrix of the graph at a randomly chosen point. The algorithm has the additional advantage of being easily parallelizable. The problem of coming up with a deterministic version of this algorithm remained open for over 35 years until it was solved in 2015 by Rohit Gurjar, Stephen Fenner and Thomas Thierauf. We will see this algorithm.

We will see a recent result of Thomas Rothvoss, that gives a constructive proof of a classical theorem in combinatorial discrepancy theory due to Spencer. Roughly, the problem is to colour the elements of a finite universe U red and blue so that each of a collection C of subsets has as small a discrepancy between the number of red and blue elements in it. Spencer showed that when |U| = |C| = n, the discrepancy can be made as small as O(\sqrt{n}). For a long time, it remained an open problem to give a constructive proof of this theorem, until a solution was provided by Nikhil Bansal in 2010. An alternate proof of Spencer's theorem was provided by a result of Lovett and Meka in 2012, and this result is generalized in the work of Rothvoss from 2014, which I will describe.

One way to describe a class of graphs closed under taking induced subgraphs is by listing the set of all forbidden graphs, graphs that are not in the class but whose every proper induced subgraph is in the class. Such characterizations are known for some important classes. The class of perfect graphs is a prime example. I will mention such a theorem that we discovered recently for a generalization of threshold graphs. Then I will discuss ongoing work on finding such a characterization for quasi-triangulated graphs, a class halfway between chordal and weakly chordal graphs. The difficult question of whether anything can be said for a general hereditary class will be pointed out. This is joint work with Richard Behr and Thomas Zaslavsky.

Edge ideals of graphs and the relation between their algebraic properties and the graph invariants is receiving a lot of attention in the recent years. In this talk we present improved lower bound for the regularity of the binomial edge ideals of trees. We then prove an upper bound for the regularity of the binomial edge ideals proposed by Saeedi Madani and Kiani for a subclass of block graphs, which in particular contain lobsters. We further show that except for trees containing what we call a jewel as a subgraph, the regularity is one more than the number of internal vertices. This talk is based on a joint work with my colleagues A V Jayanthan and B V Raghavendra Rao.

When can the rows and columns of a non-negative square matrix be scaled so that it becomes doubly stochastic? In 1964, Sinkhorn proposed and analyzed a natural iterative procedure that produces such a scaling when possible. In this talk, we will see this procedure and see some algorithmic and (if time permits) combinatorial Applications.

We will give a combinatorial proof of a product formula for the number of spanning trees of the n-dimensional hypercube. The proof we will present is a simplified version of the proof given by Bernardi.