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
Abstract:
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).
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
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.
Title: A mathematician's necklace.
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.
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
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.
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.
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.
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.
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.
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---------
Speaker : Prof Manoj Changat, University of Kerala.
Title: A new class of graphs from Posets
Abstract
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.
Speaker : Sounaka Mishra, IITM
Title: Approximation algorithms based on Primal-Dual Method
Abstract
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.
Speaker : Srivathsan Balaguru, Assistant Professor, Chennai Mathematical Institute
Title: Zero-One Law for First Order Logic on Graphs
Abstract
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.
Speaker : Vaidyanathan Sivaraman, Riley Assistant Professor, State University of NewYork, Binghamton
Title: Flexibility of embeddings of graphs on the projective plane
Abstract
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.
Speaker : Prof Arindama Singh, MA, IITM
Title: Sisyphus in front of the mirror of Erised
Abstract
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".
Speaker : N Narayanan, MA, IITM
Title: Beauty in abundance: two proofs of perfect graph theorem. part-1.
Abstract
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.
Speaker : Prof R Ramanujam, IMSc
Title: Axiom of choice: it's so obvious that it's a puzzle.
Abstract
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.
Speaker : C S Rahul, CSE, IITM
Title: An Algorithm for a special case of Connected $f$-Factors
Abstract
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.
Speaker : N S Narayanaswamy, CSE, IITM
Title: Consecutive ones property in matrices
Abstract
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.
Speaker : Saket Saurabh, IMSc
Title: Erdos Posa Theorems
Abstract
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.
Speaker : Mathew Francis
Title: Colourful Paths in Graphs (Part 2)
Abstract
The talk will continue with where we stopped last time (see below for abstract).
Speaker : Sajin Koroth (CSE, IITM)
Title: Introduction to Algebraic Graph Theory
Abstract
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.
Speaker : Mathew Francis (ISI Chennai)
Title: Colourful Paths in Graphs
Abstract
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.
hSmSeModFgg8BBStIh3xZP9E2kCggfnKhVoK1454cIc=.html