Weekly Seminar series on combinatorics

Time and Venue: 3:00 pm to 4:00 pm @ Madhava Hall (HSB 357) every Tuesday.

Legend:= Blue : Present ; Red: Future; Black : Past

Next Talk

Speaker: Prof. R Ramanujam, IMSc, Chennai.

Title: Who is afraid of infinite state systems.

Date, Time, Venue: 30/03/2017 (Thursday). 3pm-4pm. Madhava Hall (HSB 357).

Abstract: Rice's theorem states that any non-trivial property of recursive sets is undecidable, and the halting problem is the generic undecidable problem. And yet, a paper in CACM 2009 observes in its sub-title, {\em in contrast to popular belief, proving termination is not always impossible}. The new century has seen many new results proving termination for specific classes of infinite state systems. In this talk, we present one technique, namely the use of well-quasi orders for proving termination. We illustrate it with an old proof that has led many recent applications.

Upcoming Talks

Speaker : S Viswanath, IMSc, Chennai.

Title:Chromatic polynomials of graphs and words in commutation monoids.

Date, Time, Venue: 4th April 2017, 3:00pm-4pm, Madhava Hall.

Abstract:The chromatic polynomial $\chi_G(q)$ of a graph $G$ is the number of proper colourings of its vertices with $q$ colours. The commutation monoid, or trace monoid, associated to $G$ was defined by Cartier and Foata in 1969. One starts with the alphabet consisting of the vertices of $G$; the commutation monoid is the set of all words in this alphabet where two letters (vertices) are allowed to commute if there is no edge between them. I will explain what chromatic polynomials and commutation monoids have to do with each other. In particular, an interpretation of the coefficients of the chromatic polynomial in terms of the commutation monoid will be given. This point-of-view stems from Xavier Viennot's recently concluded lecture course: commutations and heaps of pieces at IMSc.

Speaker: Samrith Ram, Harish Chandra Research Institute, Allahabad.

Date, Time, Venue: 07/03/2017. Tuesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Splitting Subspaces of Linear Transformations over Finite Fields

Abstract: Let $m, n$ be positive integers and denote by $F_q$ the finite field with $q$ elements. Let $V$ be a vector space of dimension $mn$ over $F_q$ and $T : V \mapsto V$ be a linear transformation. An $m$-dimensional subspace $W$ of $V$ is said to be $T$-splitting if $V = W \oplus TW_i\oplus \ldots \oplus T^{n−1}W$. Determining the number of $m$-dimensional $T$-splitting subspaces for an arbitrary transformation $T$ is an open problem closely related to many problems in combinatorics and cryptography. I will outline con- nections with a theorem of Philip Hall on conjugacy class size in the general linear group and some results of Wilf et al. on the probability of coprime polynomials over finite fields. I will also discuss a general enumeration problem on matrix polynomials which, if solved, would settle the problem of counting $T$-splitting subspaces.

Speaker: Prof. S Viswanath, IMSc, Chennai.

Date, Time, Venue: 04/04/2017. 3pm-4pm. Madhava Hall (HSB 357).

Title: TBA

Abstract: TBA

Past Talks

Speaker: Suresh Dara, IMSc<

Date, Time, Venue: 02/03/2017. Thursday, 4.10pm to 5.10pm. Madhava Hall (HSB 357).

Title: On Erdos-Faber-Lovasz Conjecture.

Abstract: In 1972, Erdos - Faber - Lovasz (EFL) conjectured that, if $\textbf{H}$ is a linear hypergraph consisting of $n$ edges of cardinality $n$, then it is possible to color the vertices with $n$ colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erdos and Frankl had given an equivalent version of the same for graphs: Let $G= \bigcup _{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ \dots , A_n$, each having exactly $n$ vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of $G$ is $n$. The clique degree $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |\{A_i: v \in V(A_i), 1 \leq i \leq n\}|$. In this presentation we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdös - Faber - Lovász conjecture using intersection matrix of the cliques $A_i$'s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that:
1. If $G$ is a graph satisfying the hypothesis of the Conjecture and every $A_i$ ($1 \leq i \leq n$) has at most $\sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable.
2. If $G$ is a graph satisfying the hypothesis of the Conjecture and every $A_i$ ($1 \leq i \leq n$) has at most $\left \lceil {\frac{n+d-1}{d}} \right \rceil$ vertices of clique degree greater than or equal to $d$ ($2\leq d \leq n$), then $G$ is $n$-colorable.

Speaker: Suchismita Mishra, IIT Madras.

Date, Time, Venue: 31/01/2017. Tuesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title:A counterexample to Steinberg conjecture

Abstract: The famous planar four colour theorem states that every palanr graph is vertex 4-colourable. While for 1-and 2 colours answer is trivial, one can still ask, which of them need only 3 -colours. Steinberg conjectured that every planar graph that does not contain cycles of length 4 or 5 are -3 colourable. An avelanchee of partial results results showed that planar graphs without cycles of length {4,5,6,...11} , then {4,...,10} etc till {4,..7} are three colourable. We present a sketch of the method used to prove these results with a counterexample to the original conjecture.

Speaker: Dr. Biplab Basak, IISc Bangalore.

Date, Time, Venue: 25/10/2016. Tuesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: 3-colored graphs and classification of surfaces.

Crystallization is a graph-theoretical tool to study topological and combinatorial properties of PL manifolds. Motivated by the theory of crystallizations, we consider an equivalence relation on the class of 3-regular colored graphs. In this talk, we shall prove that up to this equivalence (a) there exists a unique contracted 3-regular colored graph if the number of vertices is $4m$ and (b) there are exactly two such graphs if the number of vertices is $4m+2$ for $m\geq 1$. Using this, we shall present a simple proof of the classification of closed surfaces. At the end of this talk, we shall discuss some important properties and results of crystallization in higher dimension. Then, we shall quickly go through the higher dimensional analog of genus, namely regular genus.

Speaker: Dr. Amaldev Manuel

Date, Time, Venue: 05/10/2016. Wednessday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Countable linear orderings and the Variety DA

Countable linear orderings are linear orderings over countable domains. They are of special interest because Monadic Second-order Logic is decidable over them but undecidable over arbitrary orders (in particular over the Reals). In the talk I will describe semigroups and algebras for dealing with countable orderings and their varieties. If time permits I will describe an extension of Variety DA of finite monoids to these algebras.

Speaker: Geetha Thangavelu

Date, Time, Venue: 28/09/2016. Wednessday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Schur-Weyl duality and Diagram algebras.

Abstract: Schur-Weyl duality is the foundational result in representation theory which connects the representation theory of general linear groups and the symmetric groups. Its classical version due to Issai Schur (1901 and 1927) can be viewed as an another formulation of first and second fundamental theorem of invariant theory for general linear group. After Schur's work several attempts have been made to study the analogues of this duality. In this talk we will see an important class of diagram algebras arising from this duality in connection to Lie theory, quantum groups and statistical mechanics and my recent work in this direction.

Speaker: Dr. S P Suresh

Date, Time, Venue: 22/09/2016. Thursday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Indian classical epistemology : An introduction

Two questions have consumed philosophers and thinkers for centuries – “What exists?” (ontology) and “How do we know?” (epistemology). These questions are central in the darshana tradition. In this lecture, we give a basic introduction to epistemology (pramaaNashaastra) from the point of view of the Nyaya tradition, with special emphasis on anumaana (logical inference).

Speaker: Prof. T Parthasarathy.

Date, Time, Venue: 07/09/2016. Wednesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Stochastic Games and Dubins-Savage selection lemma

Abstract: In this talk we prove optimal stationary strategies exist for zerosum stochastic games when the state space is uncountable infinite using a powerful lemma due to Dubins and savage. Such a result may not be valid in the nonzero sum stochastic games.

Speaker: Meghana Nasre, CSE, IIT Madras.

Date, Time, Venue: 31/08/2016. Wednesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: TBA


Past Talks

Speaker: Dr. T Karthick, ISI Chennai.

Date, Time, Venue: 24/08/2016. Wednesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: The maximum weight independent set problem.

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. In 1982, Alekseev showed that the M(W)IS problem remains NP-complete on H-free graphs, whenever H is connected, but neither a path nor a subdivision of the claw. In this talk, we will focus on H-free graphs, where H is a path nor a subdivision of the claw, and show that the MWIS problem can be solved in polynomial time in certain classes of these graphs.

Speaker: Dr. Madhusudan Manjunath, School of Mathematical Sciences at Queen Mary University of London.

Date, Time, Venue: 17/08/2016. Wednesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

Title: Combinatorial Riemann-Roch Theorems.

Abstract: This is an introduction to Riemann-Roch theory for graphs due to Baker and Norine. We focus on connections to combinatorial commutative algebra. Alexander duality, free resolutions: finite and infinite make an appearance. This talk is based on joint work with i. Bernd Sturmfels, ii. F-O Schreyer and John Wilmes, and iii. Alex Fink.

Speaker: Dr. Vaidyanathan Sivaraman, University of Binghamton.

Date, Time, Venue: 16/08/2016. Tuesday, 4.00pm to 5.00pm. Madhava Hall (HSB 357).

Title. Forbidden Induced Subgraph Characterizations

Abstract: 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.

Speaker: N Narayanan

Title: Let's party: Some 5-minute conjectures in graph theory.

Date, Time, Venue: 10/08/2016. Wednesday, 3.00pm to 4.00pm. Madhava Hall (HSB 357).

We go partying today - merry go around, cops and robbers, open a deck of paying cards, but mind you minors are not allowed :). Want to join? -- Some of the most intriguing conjectures in mathematics are from Combinatorics, in particular graph theory. Often it is the case that the simpler it is to state, the harder it is to solve. We present a few of these conjecuters which takes a few minutes to undertand (with their current progress), yet still stand tall unsolved. It is an invitation to research in graph theory : are you ready for the challenge?

Speaker: Prof. M S Raghunathan

Title: The Prime Number Theorem

Date, Time, Venue: 18/Apr/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: The Prime Number Theorem is arguably the most celebrated theorem in Number Theorem. It was proved in 1896 by the French mathematician J Hadamard and independently by the Belgian C de la Vallee Poussin in 1896. Both of them showed that the Riemann Zeta function has no zeros on the line $\{z | Re z =1 \}$ and deduced from this the assymptotic behaviour of $\pi (x)$ (the number of primes less than or equal to $x$) viz. that $\pi (x)/(x/log x)$ tends to 1 as $x$ tends to infinity. This last deduction was rather complicated. A much pleasanter proof was devised by D J Newman in 1980. In this talk we will present a proof of the non-vanishing of the Zeta function on $Re z =1 $ followed by Newman's simple deduction of the Prime number Theorem from it.

Speaker: Prof Kamal Lodaya, IMSc, Chennai.

Title: Courcelle's theorem

Date, Time, Venue: 11/Apr/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: Consider a property of finite graphs written in predicate logic, even allowing quantifiers over sets of vertices and edges. Courcelle (1990) gives an algorithm to check such a property which is linear in the size of the graph, parameterized by a computable function in the treewidth of the graph and the size of the formula describing the property. (Sometimes this is described as a fixed parameter linear time algorithm.) This talk gives a gentle introduction to the logic and the algorithm.

Speaker: Prof K V Subrahmanyam, Chennai Mathematical Institute.

Title: An introduction to Invariant theory.

Date, Time, Venue: 4/Apr/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: Invariant theory has been at the cornerstone of the development of algebraic geometry and representation theory in modern day mathematics. We will give a brief introduction to the subject, starting with fundamental questions posed by Hilbert in the beginning of the $20^{\rm{th}}$ century. We will then give answers to many of these questions in the concrete example of $m$-tuples of $n \times n$ matrices under the simultaneous action of $SL(n) \times SL(n)$ on the left and the right. Time permitting we will discuss the importance of invariant theory to the fundamental lower bound problems of Complexity theory in the Geometric Complexity Theory program of Ketan Mulmuley and Milind Sohoni.

Speaker: Prof V Arvind, IMSc, Chennai

Title: Efficient permutation group computation

Date, Time, Venue: 21/Mar/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: Given a subgroup $G$ of $S_n$ by a generating set and an element $g \in S_n$, we will discuss an efficient algorithms for testing if $g$ is in $G$. As a consequence, we will be able to solve a number of other algorithmic problems, e.g. solvability and nilpotence testing, random sampling from $G$.

Speaker: Shaiju A J

Title: Matrix Games

Date, Time, Venue: 14/Mar/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: This talk aims to introduce basic concepts in matrix games.In particular we discuss the definition and existance of Nash equilibrium.Furthermore, connections with linear programming will also be discussed.

Speaker: A Venkateswarlu, ISI Chennai

Title: Acyclic Edge-Coloring of Complete Bipartite Graphs

Date, Time, Venue: 07/Mar/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).


An acyclic edge-coloring of a graph is a proper edge-coloring without bi-chromatic ($2$-colored) cycles. The acyclic chromatic index of a graph $G$, denoted by $a'(G)$, is the least integer $k$ such that $G$ admits an acyclic edge-coloring using $k$ colors. In this talk we discuss some results on the acyclic chromatic index of complete bipartite graphs $K_{n,n}$ with $n$ vertices on each side. The main tool in our results/proofs is perfect $1$-factorization of $K_{n,n}$. First we present a general framework to possibly get an acyclic edge-coloring of $K_{n,n}$ which possesses a perfect $1$-factorization using $n+2$ colors. In this general framework, using number theoretic techniques, we show that $K_{n,n}$ admits an acyclic edge-coloring with $n+2$ colors for $n = \{p, 2p-1, p^2\}$, where $p$ is an odd prime.

Past talks

Speaker: N Narayanan, IITM.

Title: An infinite flock of pigeons.

Date, Time, Venue: 22/Feb/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: We take a glimpse of the pigeonhole principle in its infinite avatar. We prove the Bolzano - Weierstrass theorem and some generalisations from analysis using infinite P. H. P. We then use it to prove that circle has the most area among all figures with same perimeter.

Speaker: Prof. T Karthick, ISI Chennai.

Title: Star coloring of graphs.

Date, Time, Venue: 8/Feb/2016. Monday, 3:00pm to 4:00pm. Madhava Hall (HSB 357).

Abstract: A coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that no two adjacent vertices receive the same color. The set of vertices with the same color is called a color class. A star coloring of a graph $G$ is a coloring of $G$ such that the union of any two color classes induce a star forest. That is, a coloring of $G$ such that no path on four vertices is bi-colored. The star chromatic number of $G$ is the minimum number of colors required to star color $G$, and is denoted by $\chi_ s(G)$. The computation of $\chi_ s(G)$ is NP-hard in general. In this talk, we present some general bounds for $\chi_ s$, and then use it to derive bounds for $\chi_ s$ in certain graph classes.

Speaker: Prof. R. Balasubramanian, The Institute of Mathematical Sciences, Chennai.

Title: Additive Combinatorics

Date, Time, Venue: 1/Feb/2016. Monday, 3:30pm to 4:30pm. HSB 357.

Abstract: Additive combinatorics is a subject that deals with the combinatorics in the ring of integers or in a finite abelian group. After the path breaking works of Tao and Green , many interesting developments have taken place . We shall touch upon a few of these developments.

Speaker : N Narayanan, IITM (Math dept)

Abstract: The necklace of prayer beads a mathematician would like to wear is composed of open problems on which he can meditate up on. We will exhibit some of the beads from this necklace in this talk: Essentially a few open problems.

20/10/2015 (Tuesday)

Speaker: Prof. Suresh Govindarajan, Dept. of Physics, IITM.

Title: An excursion into the world of higher-dimensional partitions

Abstract: MacMahon introduced a higher dimensional generalisation of the partition of (positive) integers -- these are called higher-dimensional partitions. The usual partitions are line or one-dimensional partitions. Two-dimensional partitions are also called plane partitions. Explicit formulae for generating functions, due to Euler and McMahon, are known only for the numbers of line and plane partitions of integers. By considering partitions in all dimensions on the same footing, we first discuss two refinements of the counting problem -- the first one is a 1967 result of Atkin, et al.[1] which implies that, for a fixed positive integer, n, one needs (n-1) independent numbers. The second refinement[2], a 2012 result of mine, implies that one only needs [(n-1)/2] independent numbers. The first refinement appears as a binomial transform while the second refinement is a more complicated transform. We conclude with a few related conjectures that need proof as well as a combinatorial interpretation.
1. A.O.L. Atkin, P. Bratley, I.G. Macdonald, and J.K.S. McKay, Some computations for m-dimensional partitions, Proc. Cambridge Philos. Soc. 63 (1967) 1097—1100.
2. Suresh Govindarajan, Notes on Higher Dimensional Partitions, arXiv:1203.4419, Journal of Combinatorial Theory, Series A 120 (2013) 600–622.
3. Partitions of integers in any dimension and for all integers $\leq 26$ : http://www.physics.iitm.ac.in/~suresh/partitions.html
4. The partitions project at IIT Madras: http://boltzmann.wikidot.com/the-partitions-project

14/10/2015 (Wednesday)

Speaker : Dr. N Sadagopan, IIITDM Kancheepuram.

Title:Complexity of Steiner Tree in Split Graphs - Dichotomy Results

Abstract: Given a connected graph $G$ and a terminal set $R \subseteq V(G)$, Steiner tree asks for a tree that includes all of R with at most $r$ edges for some integer $r \ge 0$. It is known from [ND12,Garey et. al [1]] that Steiner tree is NP-complete in general graphs. Split graph is a graph which can be partitioned into a clique and an independent set. K. White et. al [2] has established that Steiner tree in split graphs is NP-complete. In this talk, we present an interesting dichotomy: we show that Steiner tree on $K_{1,4}$-free split graphs is polynomial-time solvable, whereas, Steiner tree on $K_{1,5}$-free split graphs is NP-complete. We investigate $K_{1,4}$-free and $K_{1,3}$-free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for Steiner tree in $K_{1,4}$-free and $K_{1,3}$-free split graphs.

7/10/2015 (Wednesday)

Speaker : Dr. Prem Lakshman Das, SETS, Chennai.

Title: Key exchanges in cryptology

Abstract: Key exchange play a vital role in cryptography. We will explore how a cyclic group can be used to achieve this. We will discuss a few examples which are used in real-life protocols.


Speaker: Narayanan, IITM

Title: Story of a colouring problem - a talk on the history of one of the simplest unsolved problems.

Abstract: A problem that you cannot solve -- A fascinating problem combining set theory, combinatorics, measure theory and distance geometry -- I cant offer money to nice problems of other people, or I will go broke -- I would offer $1000 for its solution. These are just some of the comments from giants like Paul Halmos, Paul Erdos, Ron Graham et. al - about a 60 year old problem whose best results can be proved even by 'epsilons' in the language of Erdos. The life of a mathematician working in colouring can be more colourful than one may guess. A glimpse into their story by following a single problem.

Speaker : Prof R Rama, Dept. Mathematics, IIT Madras.

Title: Pattern Avoidance

Abstract: The enumeration of permutations with subsequence conditions is a very interesting area of combinatorics. This talk will give some simple arguments for such enumerations.

16/09/2015 (Wednesday)

Speaker : Prof. R Ramanujam, The institute of Mathematical Sciences, Chennai

Title: memoryless determinacy of parity games

Abstract: infinite two-player games of perfect information have been studied by set theorists and topologists since the 1930's, and the axiom of determinacy plays an important role in modern descriptive set theory. a subclass of these games have turned out to be of great significance in theoretical computer science. work on this line proceeds by reducing the problem of designing a system to work successfully in uncertain environments to the synthesis of winning strategies in appropriately designed in infinite games. determinacy also relates to complementation of automata on infinite trees. these lectures hope to provide a short introduction to this area of research.

10/09/2015 (Thursday )

Speaker : Prof. R Ramanujam, The institute of Mathematical Sciences, Chennai

Title: infinite games on finite graphs: applications

Abstract: infinite two-player games of perfect information have been studied by set theorists and topologists since the 1930's, and the axiom of determinacy plays an important role in modern descriptive set theory. a subclass of these games have turned out to be of great significance in theoretical computer science. work on this line proceeds by reducing the problem of designing a system to work successfully in uncertain environments to the synthesis of winning strategies in appropriately designed in infinite games. determinacy also relates to complementation of automata on infinite trees. these lectures hope to provide a short introduction to this area of research.


Speaker : Prof. R Ramanujam, The institute of Mathematical Sciences, Chennai

Title: infinite games in formal verification: gale-stewart games and determinacy

Abstract: infinite two-player games of perfect information have been studied by set theorists and topologists since the 1930's, and the axiom of determinacy plays an important role in modern descriptive set theory. a subclass of these games have turned out to be of great significance in theoretical computer science. work on this line proceeds by reducing the problem of designing a system to work successfully in uncertain environments to the synthesis of winning strategies in appropriately designed in infinite games. determinacy also relates to complementation of automata on infinite trees. these lectures hope to provide a short introduction to this area of research.


Speaker: Dr. Amrinanshu Prasad

Title: Odd Dimensional Representations in Young's Lattice

Abstract: Young's lattice is the graph whose vertices are Integer Partitions. Two partitions are connected by an edge if they differ in one part, and the difference in that part is equal to one.

An important statistic of an Integer Partition is the so-called f-statistic, which is given by the celebrated hook-length formula of Frame, Robinson and Thrall. This statistic can be interpreted as the dimension of a representation of a symmetric group. Macdonald has characterized integer partitions with odd f-statistic.

In this talk, we will explain Macdonald's characterization of partitions with f-statistic. We will also show that the vertex induced subgraph of Young's lattice consisting of partitions with odd f-statistic is a binary tree. The results and their proofs are purely combinatorial, and no background in representation theory is expected.

: 19/08/2015

Speaker : Dr. Ignazio Longhi

Title: Analytic and topological approaches to prime numbers

Abstract: We will survey some topics related to the "amount" of prime numbers and approaches to this kind of question using analytic and topological ideas. For example, one can prove that there are infinitely many primes using analytic tools (the zeta function) or topology (taking the profinite completion of the integers). Similarly, one can look for a topological version of Dirichlet's theorem that there are infinitely many primes in arithmetic progressions. The talk should be largely elementary and accessible to undergraduates.

Note: This is not relly a discrete mathematics talk, but will be accessible and interesting to all.

: 12/08/2015

Speaker : Dr. Mathew Francis, ISI Chennai

Title: Boxicity of graphs

Abstract: A $k$-dimensional box, or "$k$-box" for short, is the Cartesian product of $k$ closed intervals on the real line. For example, a $2$-box is an axis-parallel rectangle on the plane and a $3$-box is a cuboid in space with its edges parallel to the axes. The boxicity of a graph $G$ is the minimum integer $k$ such that each vertex of $G$ can be assigned a $k$-box in such a way that two vertices of $G$ are adjacent if and only if their corresponding $k$-boxes intersect. It can be easily seen that the graphs of boxicity $1$ form exactly the well-known class of interval graphs. In this talk, we shall discuss some basic results about the boxicity of graphs.

-------Semester break---------

: 28/04/2015

Speaker : Prof Manoj Changat, University of Kerala.

Title: A new class of graphs from Posets


Cover graphs and Comparability graphs are two well known graphs from posets. Characterization of cover graphs is still not known while comparability graphs have nice characterizations and also they can be recognized in polynomial time. Here a new class of graphs from posets is introduced and some basic results and some problems on these graphs is presented.

: 23/04/2015

Speaker : Sounaka Mishra, IITM

Title: Approximation algorithms based on Primal-Dual Method


In this talk we will first overview the generic method of designing an approximation algorithm for NP-complete optimization problems. Then we will describe a factor 2 approximation algorithm for Minimum Feedback Vertex Set and other problems.

: 09/04/2015

Speaker : Srivathsan Balaguru, Assistant Professor, Chennai Mathematical Institute

Title: Zero-One Law for First Order Logic on Graphs


Given an undirected graph, is it triangle-free? Does it have isolated vertices? These are the kind of questions that can be formulated using first order logic (FOL). An FOL formula evaluates to either true or false on a graph. The zero-one law for FOL says that every FOL formula either evaluates to true on "almost" all graphs, or evaluates to false on "almost" all of them. The talk will be a gentle introduction to FOL followed by a proof-sketch of the zero-one law.

: 26/03/2015

Speaker : Vaidyanathan Sivaraman, Riley Assistant Professor, State University of NewYork, Binghamton

Title: Flexibility of embeddings of graphs on the projective plane


Abstract: Planar graphs have been a major topic of interest in graph theory, thanks to the four-color problem. The importance of understanding graphs embedded on surfaces became clear after the groundbreaking work of Robertson and Seymour in connection with their work on Wagner's conjecture. I will address the following question: Is there a complete set of operations that can explain different embeddings of a nonplanar graph on the projective plane? This is joint work with John Maharry, Neil Robertson and Daniel Slilaty.

: 19/03/2015

Speaker : Prof Arindama Singh, MA, IITM

Title: Sisyphus in front of the mirror of Erised


As the myth goes, Sisyphus was cursed to carry a heavy piece of stone to the top of a hill; and as soon as he places it there, the stone rolls back to the ground. Once again he carries it to its intended place. In the mirror of Erised, one is supposed to see one's own desires throwing open the casket of bad faith. When Sisyphus looks at the mirror of Erised, in the background of a rich formal system, all sorts of paradoxes appear. We will not enter the labyrinth of paradoxes, for the weird mirror might drive us to insanity. We will rather take help from a small machine "SisEr" to walk around the labyrinth. The machine works with just four symbols and poses a puzzle to the arrogant mathematician. We will show how the puzzle crushes the arrogance of the mathematician leading him/her to realize the limitations. The mathematician sees clearly that his/her god called "proof" is just incapable of catching the "truth".

: 12/03/2015

Speaker : N Narayanan, MA, IITM

Title: Beauty in abundance: two proofs of perfect graph theorem. part-1.


The proof of perfect graph theorem is unsurpassed in its elegence and one that shows the 'feel' for the problem in designing the proof. We discuss this beautiful proof in the first talk. The second proof is another elegent linear algebra proof given by Gasparian, which we will discuss in a later lecture. A graph is perfect if the chromatic number and size of largest clique coincide for every induced subgraph. The perfect graph therem states that a graph is perfect iff its complement is perfect.

: 5/03/2015

Speaker : Prof R Ramanujam, IMSc

Title: Axiom of choice: it's so obvious that it's a puzzle.


The axiom of choice asserts that any nonempty product of nonempty sets is nonempty. This seems so trite, it is amazing that there should be any controversy at all in accepting it. It seems unnecessary to state as an axiom, it ought to follow from the other axioms of set theory; but it doesn't, and has many surprising counter-intuitive consequences.

If set theorists are interested in models of set theory in which choice fails, it is for good reason: you can prove theorems by starting with models in which strong combinatorial principles hold that negate choice. Some of these (e.g. the axiom of determinacy of games) are interesting in themselves. Further, given strong enough assumptions about large cardinals, there are natural models in which choice fails spectacularly. So the advice is: do assume the axiom of choice, but do not be complacent about it.

The talk is a basic introduction (and invitation) to this fascinating world.

: 26/02/2015

Speaker : C S Rahul, CSE, IITM

Title: An Algorithm for a special case of Connected $f$-Factors


Given and edge weighted undirected graph $G=(V,E)$ with $|V|=n$, and a function $f: V \mapsto \mathbb{N}$, we consider the problem of finding a connected $f$-factor in $G$. In particular, for each constant $c\ge 2$, we consider the case when $f(v)\ge \frac{n}{c}$, for all $v$ in $V$. We characterize the set of graphs that have a connected $f$-factor for $f(v) \ge \frac{n}{3}$, for every $v$ in $V$, and this gives a polynomial time algorithm for the decision version of the problem. Extending the techniques, we solve the minimization version.

: 19/02/2015

Speaker : N S Narayanaswamy, CSE, IITM

Title: Consecutive ones property in matrices


We introduce and present a characterization of the matrix consecutive ones property. We also talk about an natural optimization problem related to the consecutive ones property. We then pose some open questions.

: 12/02/2015

Speaker : Saket Saurabh, IMSc

Title: Erdos Posa Theorems


In graph-theory Erdos Posa theorems correspond to the results of the following type: For every positive integer $k$, either a graph has $k$ vertex disjoint structures or has a $f(k)$ sized vertex subset which intersects every structure. For an example, take cycles or grids in graph as structure. In this talk we will see origin to some of these results and will also see some of the modern development.

: 5/02/2015

Speaker : Mathew Francis

Title: Colourful Paths in Graphs (Part 2)


The talk will continue with where we stopped last time (see below for abstract).

: 29/01/2015

Speaker : Sajin Koroth (CSE, IITM)

Title: Introduction to Algebraic Graph Theory


One of the natural representation of a graph is using its adjacency matrix. A lot of interesting graph theoretic properties can be better understood by studying the underlying matrix and its linear algebraic properties. We will introduce at least one such connection, i.e., the connection between second largest eigen value of the adjacency matrix and a graph theoretic parameter ``called expansion''. We will also see how to exploit these connections between algebraic / combinatorial parameters with some illustrative proofs and algorithms. As we are just starting off the seminar series the talk would be placed at an introductory level.

: 22/01/2015

Speaker : Mathew Francis (ISI Chennai)

Title: Colourful Paths in Graphs


A "proper vertex colouring" of a graph is an assignment of labels (or "colours") to the vertices of a graph such that no two adjacent vertices get the same label. The minimum number of colours required in any proper vertex colouring of a graph $G$ is known as its chromatic number, denoted by $\chi(G)$. In a properly vertex coloured graph, we say that a path is a "colourful path" if no two vertices on the path have the same colour. Given a properly vertex coloured graph, it is known that there is always a colourful path on $\chi(G)$ vertices in it. We conjecture that given any properly vertex coloured triangle-free graph, there is an induced colourful path on $\chi(G)$ vertices in the graph and look at various aspects of this conjecture. This talk will be at introductory level.