[csdm-rutgers] Theoretical Computer Science/Discrete Math Seminars -- Week of September 22, 2014

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of September 22, 2014


--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------

Monday, September 22

Computer Science/Discrete Mathematics Seminar I
Topic: 		Colouring graphs with no odd holes
Speaker: 	Paul Seymour, Princeton University
Time/Room: 	11:15am - 12:15pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=52284



Tuesday, September 23

Computer Science/Discrete Mathematics Seminar II
Topic: 		Uniform words are primitive
Speaker: 	Doron Puder, Member, School of Mathematics
Time/Room: 	10:30am - 12:30pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=52414

1 Colouring graphs with no odd holes
    Paul Seymour

The chromatic number \(k(G)\) of a graph \(G\) is always at least the 
size of its largest clique (denoted by \(w(G)\)), and there are graphs 
with \(w(G)=2\) and \(k(G)\) arbitrarily large. On the other hand, the 
perfect graph theorem asserts that if neither \(G\) nor its complement 
has an odd hole, then \(k(G)=w(G)\). (An ``odd hole" is an induced cycle 
of odd length at least five.) What happens in between? With Alex Scott, 
we have just proved the following, a 1985 conjecture of Gyarfas: For 
graphs \(G\) with no odd hole, \(k(G)\) is bounded by a function of 
\(w(G)\).

http://www.math.ias.edu/seminars/abstract?event=52284

2 Uniform words are primitive
    Doron Puder

Let \(G\) be a finite group, and let \(a\), \(b\), \(c\),... be 
independent random elements of \(G\), chosen at uniform distribution. 
What is the distribution of the element obtained by a fixed word in the 
letters \(a\), \(b\), \(c\),..., such as \(ab\), \(a^2\), or 
\(aba^{-2}b^{-1}\)? More concretely, do these new random elements have 
uniform distribution? In general, a word \(w\) in the free group \(F_k\) 
is called uniform if it induces the uniform distribution on every finite 
group \(G\). So which words are uniform? A large set of uniform words 
are those which are 'primitive' in the free group \(F_k\), namely those 
belonging to some basis (a free generating set) of \(F_k\). Several 
mathematicians have conjectured that primitive words are the only 
uniform words. In a joint work with O. Parzanchevski, we prove this 
conjecture. I will try to define and explain all notions, and give many 
details from the proof. I will also present related open problems.

http://www.math.ias.edu/seminars/abstract?event=52414

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdmrutgers/attachments/20140916/2049a3a0/attachment.html>