- You are here:
- GT Home
- Home
- News & Events

Thursday, February 14, 2019 - 11:00 ,
Location: Skiles 006 ,
Dhruv Mubayi ,
University of Illinois at Chicago ,
Organizer: Prasad Tetali

After a brief introduction to classical hypergraph Ramsey numbers, I will focus on the following problem. What is the minimum t such that there exist arbitrarily large k-uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and every s vertices span at most t edges? Erdos and Hajnal conjectured (1972) that this minimum can be calculated precisely using a recursive formula and Erdos offered $500 for a proof. For k=3, this has been settled for many values of s, but it was not known for larger k. Here we settle the conjecture for all k at least 4. Our method also answers a question of Bhatt and Rodl about the maximum upper density of quasirandom hypergraphs. This is joint work with Alexander Razborov.

Thursday, November 2, 2017 - 11:05 ,
Location: Skiles 006 ,
Joel Spencer ,
Courant Institute, New York University ,
Organizer: Lutz Warnke

Traditional Erdos Magic (a.k.a. The Probabilistic Method) proves the existence of an object with certain properties by showing that a random (appropriately defined) object will have those properties with positive probability. Modern Erdos 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 Erdos 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 ,
tomasz@amu.edu.pl ,
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:

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.