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.

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.

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.

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

Title: TBA

Abstract: TBA

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.

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.

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

Title: 3-colored graphs and classification of surfaces.

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

Title: Countable linear orderings and the Variety DA

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

Title: Schur-Weyl duality and Diagram algebras.

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

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).

Abstract:

####
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).

Abstract:#### 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 : Prof. Xavier Viennot, CNRS Emeritus Research Director, Bordeaux University, France; Adjunct Professor, IMSc, Chennai.

###
Title: The Magic of Young tableaux

### Date, Time, Venue: 11/Jan/2016. Monday, 4:00pm to 5:00pm. HSB 357.

###
Abstract:

####
Young tableaux are certain combinatorial objects introduced in relation with some considerations in algebra. Pairs of Young tableaux with the same "shape" are enumerated by n! , that is the number of permutations on n elements. A famous correspondence is the Robinson-Schensted-Knuth algorithm (or RSK) which gives a one-to-one correspondence between these pairs of Young tableaux and permutations. It can be described in various different ways.
The equivalence of these different constructions are fascinating. The famous computer scientist Donald Knuth said in 1972 "The unusual nature of these coincidences might lead us to suspect that some sort of witchcraft is operating behind the scene". This talk, accessible to every one, illustrates the nowadays style of combinatorial mathematics: visual, concrete, related to deep mathematics and magic.

### Date, Time Venue: 29/10/2015, HSB 257, 4:15 to 5:15 PM

#### Title: A mathematician's necklace.

###

### 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.

References:

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.

### 30/09/15

#### 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.

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.

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

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

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).

Abstract:

Title: The Prime Number Theorem

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

Title: Courcelle's theorem

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

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.

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$.

Title: Matrix Games

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

Abstract:

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.

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.

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.

References:

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

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.

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

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.