
Abstract by
Professor Tibor Szabó
UIUC
- Explicit vs. Probabilistic in Extremal Combinatorics.
The typical problem of extremal combinatorics can be formulated as follows: given a property P and parameter f of combinatorial structures, what is the maximum/minimum of f over all structures having property P. In most of the cases, non-deterministic methods are very succesful in providing the extremal object with the required property. However, there are a few examples where explicit constructions are more effective. They are also important for practical applications, even in cases when the existence of a much better structure is known via the probabilistic method.
In this talk we discuss the two approaches through two classic problems of combinatorics: Ramsey- and Turán-type problems.
- Thursday, November 11, 1999, 4:00 p.m. - 245 Altgeld Hall
MATHEMATICS COLLOQUIUM
Refreshments will be served in the Commons Room 321 Altgeld Hall at 3:15 p.m..
Go Back