Seminars and Colloquia by Series

Thursday, November 2, 2017 - 11:05 , Location: Skiles 006 , Joel Spencer , Courant Institute, New York University , Organizer: Lutz Warnke
Traditional Erdoes Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain propertiesby showing that a random (appropriately defined) object will have those properties with positive probability.  Modern Erdoes Magic analyzes a random process, a random (CS take note!) algorithm.  These, when successful, can find a "needle in an exponential haystack" in polynomial time. We'll look at two particular examples, both involving a family of n-element sets under suitable side conditions.  The Lovasz Local Lemma finds a coloring with no set monochromatic.  A result of this speaker finds a coloring with low discrepency.  In both cases the original proofs were not implementable but Modern Erdoes Magic finds the colorings in polynomial times. The methods are varied.  Basic probability and combinatorics. Brownian Motion.  Semigroups.  Martingales. Recursions  ... and Tetris!
Thursday, September 28, 2017 - 11:05 , Location: Skiles 006 , Tom Bohman , Carnegie Mellon University , Organizer: Lutz Warnke
The probabilistic method for constructing combinatorial objects has had a profound impact on the field since the pioneering work of Erdos in the first half of the twentieth century.  Some recent applications of the probabilistic method build objects of interest by making a series of random choices that are guided by a simple rule and depend on previous choices.  We give two examples of randomized algorithms of this type: random triangle removal and the triangle-free process.  These algorithms address the classical questions of counting Steiner triple systems and determining the minimum independence number of a triangle-free graph on n vertices, respectively.  Pseudo-random heuristics and concentration of measure phenomena play a central role in analyzing these processes.
Tuesday, February 28, 2017 - 11:05 , Location: Skiles 006 , Tomasz Ɓuczak , Adam Mickiewicz University , , Organizer: Lutz Warnke
The talk is meant to be a gentle introduction to a part of combinatorial topology which studies randomly generated objects. It is a rapidly developing field which combines elements of topology, geometry, and probability with plethora of interesting ideas, results and problems which have their roots in combinatorics and linear algebra.
Friday, November 6, 2015 - 15:05 , Location: Skiles 005 , Daniel Kral , University of Warwick , Organizer: Robin Thomas

Refreshments will be served in the atrium after the talk.

The theory of combinatorial limits provides analytic ways of representing large discrete objects. The theory has opened new links between analysis, combinatorics, computer science, group theory and probability theory. In this talk, we will focus on limits of dense graphs and their applications in extremal combinatorics. We will present a general framework for constructing graph limits corresponding to solutions of extremal graph theory problems, which led to constructing counterexamples to several conjectures concerning graph limits. At the end, we will discuss limits of sparse graphs and possible directions to unify the existing approaches related to dense and sparse graphs.
Thursday, September 26, 2013 - 16:30 , Location: Skyles 005 , Zoltan Furedi , Renyi Institute of Mathematics of the Hungarian Academy of Sciences , Organizer: Karim Lounici

Refreshements served at 4:00pm

There are many instances in Coding Theory when codewords must be restored from partial information, like defected data (error correcting codes), or some superposition of the strings.These lead to superimposed codes, close relatives of group testing problems.There are lots of versions and related problems, likeSidon sets, sum-free sets, union-free families, locally thin families, cover-free codes and families, etc.We discuss two cases {\it cancellative} and {\it union-free} codes.A family of sets $\mathcal F$ (and the corresponding code of0-1 vectors) is called {\bf union-free} if $A\cup B = C\cup D$ and $A,B,C,D\in \mathcal F$ imply  $\{ A,B\}=\{ C, D \}$.$\mathcal F$ is called $t$-{\bf cancellative}if for all distict $t+2$ members  $A_1, \dots, A_t$ and $B,C\in \mathcal F$  $$A_1\cup\dots \cup A_t\cup  B \neq A_1\cup \dots A_t \cup C.  $$Let $c_t(n)$ be the size of the largest $t$-cancellative code on $n$elements. We significantly improve the previous upper bounds of Alon, Monti, K\"orner and Sinaimeri, and introduce a method to deal with such problems, namely to investigate first the constant weight case (i.e., uniform hypergraphs).
Thursday, January 21, 2010 - 11:05 , Location: Skiles 269 , Bruce Reed , McGill University , Organizer: Robin Thomas
The term Probabilistic Method refers to the proof of deterministic statements using probabilistic tools. Two of the most famous examples arise in number theory. these are: the first non-analytic proof of the prime number theorem given by Erdos in the 1940s, and the recent proof of the Hardy-Littlewood Conjecture (that there are arbitrarily long arithmetic progressions of primes) by Green and Tao. The method has also been succesfully applied in the field of graph colouring. We survey some of the results thereby obtained. The talk is targeted at a general audience. We will first define graph colouring, explain the type of graph colouring problems which tend to attract interest, and then explain the probabilistic tools which are used to solve them, and why we would expect the type of tools that are used to be effective for solving the types of problems typically studied.
Tuesday, October 21, 2008 - 16:30 , Location: Skiles 255 , Chris Godsil , University of Waterloo , Organizer: Robin Thomas

Refreshments will be served at 4PM in Skiles 236.

The possibility of a quantum computer has lead to much new work in theoretical physics and, naturally enough, this work has raised many new mathematical problems. What is perhaps surprising is that it has lead to interesting problems in algebraic graph theory. For example, questions about the relative power of quantum computer and classical computers lead to questions about the chromatic number of certain graphs. In my talk I will discuss some of these problems, and the progress that has been made.