Math 584/CS 575 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.

• Homework 1: DUE:  February 12 (Monday); Do 5 if you plan to do research in combinatorics, and 4 otherwise (or undergraduate). Indicate it on homework.

• Homework 2: DUE:  April 6 (Friday); Do 5 if you plan to do research in combinatorics, and 4 otherwise (or undergraduate). Indicate it on homework. Note: Exercise 5= Skew Bollobas set-pair inequality

• Homework 3: DUE:  April 9 (Monday); Do 5 if you plan to do research in combinatorics. Indicate it on homework.

• Homework 4:
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.

• Nullstellensatz, textbook via Doug West
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 ****************************
********************************************************************************************
• Homework 1: DUE:  February 11 (Monday)

• Homework 2: DUE:  February 25 (Monday)

• Homework 3: DUE:  March 11 (Monday)

• Homework 4: DUE:  April 8 (Monday)

• Homework 5: DUE:  May 8 (Wednesday)

• Flag Notes I:

• Flag Notes II:

• Flag Notes III: