METHODS OF COMBINATORICS, Fall 2015

**Instructor:** Jozsef Balogh

**Office:** 233B Illini Hall

**Phone:** (217) 244-1918 (office)

**E-mail:** jobal@math.uiuc.edu

**Time and place:** 12:00- 12:50 pm MWF, 241 Altgeld Hall

**Office Hour:** by appointment.

PREREQUISITES:

Math 580 or consent of instructor, obtainable by familiarity
with elementary combinatorics.

CANCELLED CLASSES: March 27, 29, 31, April 2, 4;

MAKE UP CLASSES: May 4 Friday; 10-11 am 141 AH

;

COURSE REQUIREMENTS:

There will be 3 homework assignments. Homework allows you to choose **five out of six problems to write up.**
Problems are worth 5 points each, so the maximum score/homework is 25 points. For Math 584 students A is from 80%, grade drops by 5% (so 75% is A-), for CS 575 A is from 75%, grade drops by 5% (so 70% is A-). Make up possibilities include giving lecture.

TEXT:

Jiri Matousek: 33 Miniatures, Mathematical and Algorithmic Applications of Linear Algebra + selected research papers.

1. Write a one page typed text explaining the (basic) polynomial method for a non-combinatorialist mathematician.

2. Write a one page typed text explaining the null-stellensatz and its applications for a non-combinatorialist mathematician.

3. Write a one page typed text explaining the modern polynomial method, compare it with the basic method.

4. Prove that for every a there is a c such that if n is sufficiently large, then every graph G with n vertices and (1/4+a)n^2 edges contains at least cn^3 triangles.

5. Give reasonable good lower and upper bounds on the following: Recall f(n,a,b) is the maximum number of edges of an n-vertex 3-uniform hypergraph which contains no a vertices with at least b hyperedges. (i) f(n,7,4); (ii) f(n,5,4); (iii) f(n,5,3); (iv) f(n,6,4).

6. Continuation of 5: (a) f(n,6,6); (b) f(n,6,8); (c) f(n,6,9). Due: April 30, Monday. Do at five problems.

Also, recommended to look: Alon, Noga Combinatorial Nullstellensatz. Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comput. 8 (1999), no. 1-2, 7–29.

********************************************************************************************

************* BELOW THIS LINE IS ABOUT THE CLASS AT LEAST 3 YEARS AGO ****************************

********************************************************************************************