# Math 580 Combinatorial Mathematics, Fall 2018

Instructor:   Jozsef   Balogh
Office: 233B Illini Hall
E-mail: jobal@math.uiuc.edu
Time and place: 10:00- 10:50pm MWF, 143 Altgeld Hall.
Study Session: Wednesdays 3-5 pm 443 Altgeld hall
Office Hour: right after classes, MF 11:00- 11:50.
Make up class: November 2, Friday 3-5 pm 243 Altgeld hall
Test 1: October 24 (W) 6-8 pm covering Chapters 1--4, 243 Altgeld Hall.
Test 2: December 5 (W) 6-8 pm covering rest of the Chapters, 243 Altgeld Hall.
Classes will be cancelled (because of evening tests):
Last class is December )
Final exam: 1:30--4:30 p.m., Monday, December 17.

HOMEWORK: FALL 2018:

From each homework assigment solve five out of the six to be collected problems. The solutions should include proofs, should be readable and as self-complete as possible.

Homework 1, ,    due September 7,     Friday, before class:
Warm up problems:        Section 1.1: 1, 5, 7, 11, 12; Section 1.2: 1, 2, 3, 4, 5, 6, 10; Section 1.3: 1, 3, 4, 7.
Extra problems:            Section 1.1: 18, 26, 27, 28, 34, 35, 36, 39, 40, 41. Section 1.2: 11, 12, 13, 15, 20, 29, 34, 39. Section 1.3: 17, 18, 26, 27, 28, 29, 30, 31, 33.
Homework Problems (to be collected)       Section 1.1: 34, 40;     Section 1.2: 13, 39;     Section 1.3: 15, 31.

Homework 2,     due September 14,     Friday, before class:
Warm up problems:        Section 2.1 #1, 2, 4, 8; Section 2.2 #1, 2, 3, 7, 8, 9.
Extra problems:            Section 2.1 #12, 17--25, 32, 34, 36, 37, 43, 47, 49, 51, 53, 54, 62, 64, 66, 68; Section 2.2 #11, 23, 26, 29, 32--35, 37.
Homework Problems (to be collected)       Section 1.2: 17;    Section 1.3: 26;    Section 2.1: 12, 17, 49;    Section 2.2: 11.

Homework 3,     due September 21,     Friday, before class:
Warm up problems:        Section 2.3: 1, 2, 3, 4. Section 3.1: 1, 2, 3, 4, 7.
Extra problems:            Section 2.3: 6, 7, 8. Section 3.1: 8, 14, 15, 19, 23, 24, 27, 28, 29, 36, 37, 38, 39, 40.
Homework Problems (to be collected)       Section 2.2: 23, 34, 38;     Section 2.3: 16;     Section 3.1: 23, 35 and 36 as one problem;

Homework 4,     due September 28,     Friday, before class:
Warm up problems:        Section 3.2: 2, 3, 4, 5, 7. Section 3.3: 1, 2, 4, 7. Section 3.4: 1, 2, 3.
Extra problems:            Section 3.2: 12, 15, 18, 19, 20, 22, 25, 28, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48. Section 3.3: 13, 14, 15, 16, 19, 20, 22, 23, 24, 28, 29, 30, 31, 36, 41. Section 3.4: 7, 8, 9, 18, 19, 23, 24, 27, 28, 32, 33.
Homework Problems (to be collected)       Section 3.2: 18, 42, 44.     Section 3.3: 24, 30.     Section 3.4: 33.

Homework 5,     due October 12,     Friday, before class:
Warm up problems:        Section 4.1: 2, 3, 4, 5, 6, 9, 10; Section 4.2: 2, 3, 5; Section 4.3: 2;
Extra problems:            Section 4.1: 16, 19, 20, 21, 22, 23, 28, 29, 31, 32, 39, 40, 41, 42, 43, 46, 47. Section 4.2: 14, 15, 17, 20, 21, 25; Section 4.3: 10, 11;
Homework Problems (to be collected)       Section 4.1: 21, 31, 47;     Section 4.2: 15, 20;     Section 4.3: 11.

Homework 6,     due October 19,     Friday, before class:
Warm up problems:        Section 5.1: 6, 8, 17; Section 5.2: 1, 5; Section 5.3: 3, 5; Section 5.4: 6, 8.
Extra problems:            Section 5.1: 20, 25, 44, 45; Section 5.2: 10, 11, 13, 22, 28, 29, 31, 32, 33, 34; Section 5.3: 24, 25, 26, 27, 34, 35, 36, 37, 38, 39, 41; Section 5.4: 15, 17, 22, 25, 27, 28, 35, 36, 39, 47, 63;
Homework Problems (to be collected)       Section 5.1: 44;     Section 5.2: 10, 28; 32;     Section 5.3: 36;    Section 5.4: 28.

Homework 7,     due November 2,     Friday, before class:
Warm up problems:        Section 6.1: 1, 2, 3, 4, 6, 7. Section 6.2: 1, 3. Section 7.1: 1, 3, 8 Section 7.2: 2, 4, 5, 7, 8, 10, 14;
Extra problems:            Section 6.1: 15, 16, 18, 19, 20, 23, 29, 34, 37, 40, 46, 48, 50; Section 6.2: 5, 6, 11, 17, 19, 22, 25, 26, 32, 36, 37, 40. Section 7.1: 18, 20, 21, 23, 24, 25, 32. Section 7.2: 21, 23, 26, 28, 30, 31, 32, 38;
Homework Problems (to be collected)       Section 6.1: 19, 28;     Section 6.2: 15, 37;     Section 7.1: 25;    Section 7.2: 30.

Homework 8,     due November 9,     Friday, before class:
Warm up problems:        Section 7.3: 3, 5, 6;     Section 8.1: 4, 5, 6, 7;     Section 8.2: 1, 2, 6, 7;     Section 8.3: 3, 8, 9;
Extra problems:            Section 7.3: 7, 9, 14, 15, 19, 28, 34, 35, 36, 38, 43, 49, 50;     Section 8.1: 10, 12, 13, 16, 17, 27, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41;     Section 8.2: 15, 16, 23, 24, 25, 27, 28, 31.     Section 8.3: 13, 15, 24, 25, 26;
Homework Problems (to be collected)       Homework:     Section 7.3: 35, 49;     Section 8.1: 27, 30;     Section 8.2: 16;     Section 8.3: 15.

Homework 9,     due November 30,     Friday, before class:
Warm up problems:        Section 9.1: 9, 10, 11, 14.     Section 9.2: 1, 3, 4, 5, 6.     Section 9.3: 2, 3, 6.     Section 10.1: 1.     Section 10.2: 2.
Extra problems:            Section 9.1: 15, 17, 19, 23, 27, 30, 34, 36, 37, 38, 39, 40, 41, 43, 45, 48, 54.     Section 9.2: 8, 11, 12, 14, 15     Section 9.3: 8, 10, 11, 20, 23, 25, 26, 28, 31.     Section 10.2: 10, 13, 19, 20, 29, 31, 33.
Homework Problems (to be collected)       Homework:     Section 9.1: 34, 48     Section 9.2: 15    Section 9.3: 25, 31    Section 10.2: 26

Homework 10,     due December 10,     Monday, before class:
Warm up problems:        Section Section 11.1: 2, 3, 4.     Section 13.1: 2, 3, 5.     Section 13.1: 2, 3, 5.     Section 13.2: 4.
Extra problems:            Section Section 11.1: 6, 7, 8, 13, 14, 15, 16, 23, 25.     Section 14.1: 28, 29;     Section 14.2: 1, 2, 7, 10, 12, 13, 14     Section 13.2: 10.
Homework Problems (to be collected, do 5 out of 7 problems)       Homework:     Section 11.1: 7; 23, 39     Section 14.1: 28,     Section 14.2: 2    Section 13.2: 10.     Section 12.1: 15

HOMEWORK: FALL 2017:

From each homework assigment solve five out of the six to be collected problems. The solutions should include proofs, should be readable and as self-complete as possible.

Homework 1, ,    due September 7,     Friday, before class:
Warm up problems: nbsp;      Section 1.1: 1, 5, 7, 11, 12; Section 1.2: 1, 2, 3, 4, 5, 6, 10; Section 1.3: 1, 3, 4, 7.
Extra problems:            Section 1.1: 18, 26, 27, 28, 34, 35, 36, 39, 40, 41. Section 1.2: 11, 12, 13, 15, 20, 29, 34, 39. Section 1.3: 17, 18, 26, 27, 28, 29, 30, 31, 33. Homework Problems (to be collected)       Section 1.1: 34, 35;        Section 1.2: 15, 37,        Section 1.3: 27, 31.

Homework 2,     due September 18,     Monday, before class:
Warm up problems: nbsp;      Section 2.1: 1, 2, 4, 8.                  Section 2.2: 1, 2, 3, 7, 8, 9.
Extra problems:            Section 2.1: 12, 17, 18, 19, 20, 22, 23, 24, 25, 32, 34, 36, 37, 43, 47, 51, 53, 62, 64, 66, 68.            Section 2.2: 11, 23, 26, 29, 31, 32, 33, 34, 35, 37.            Homework Problems (to be collected)       Section 2.1: 18, 23 [official proof is using a bit iteration/recursion, just a little bit], 43;        Section 2.2: 31 [keep generating function with one variable], 33, 37 [do not get scared from quadratic equations in function of the generating function].

Homework 3,     due September 29,     Friday, before class:
Warm up problems: nbsp;      Section 2.3: 1, 2, 3, 4.                  Section 3.1: 1, 2, 3, 4, 7.         Section 3.2: 2, 3, 5, 7.
Extra problems:            Section 2.3: 8, 9, 13.            Section 3.1: 8, 14, 15, 19, 23, 24, 27, 28, 36, 39.       Section 3.2: 16, 18, 19, 20, 21, 22, 24, 25, 29, 30, 31, 32, 34, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47.
Homework Problems (to be collected)       Section 2.3: 8;        Section 3.1: 14, 19, 28;     Section 3.2: 19, 38;

Homework 4,     due October 6,     Friday, before class:
Warm up problems: nbsp;      Section 3.3: 1, 2, 4, 7.                  Section 3.4: 1, 2, 3.
Extra problems:            Section 3.3: 13, 14, 15, 16, 19, 20, 22, 23, 24, 29, 30, 35, 38, 40.            Section 3.4: 7, 8, 9, 10, 16, 19, 23, 26, 27, 28, 30, 31, 32.
Homework Problems (to be collected)       Section 3.2: 16, 40, 42;        Section 3.3: 15, 30;     Section 3.4: 28;

Homework 5,     due October 11,     Friday, before class:
Warm up problems: nbsp;      Section 4.1: 1, 2, 3, 5, 9, 10, 12;                  Section 4.2: 2, 3, 5;          Section 4.3: 3;
Extra problems:            Section 4.1: 16, 17, 20, 21, 22, 23, 24, 28, 29, 31, 33, 42, 43, 44, 45, 46, 47.            Section 4.2: 9. 10, 16, 18, 22, 25, 26;     Section 4.3: 9, 15;
Homework Problems (to be collected)       Section 3.4: 9;        Section 4.1: 29, 42, 56;     Section 4.2: 14, 22 ;

Homework 6, ,    due October 20,     Friday, before class:
Warm up problems: nbsp;      Section 5.1: 6, 8, 17;        Section 5.2: 1, 5;        Section 5.3: 2, 5;        Section 5.4: 6, 8;
Extra problems:            Section 5.1: 20, 25, 43;            Section 5.2: 10, 11, 13, 22, 28, 31, 32, 33,      Section 5.3: 24, 26, 27, 34, 35, 36, 37, 39, 41;       Section 5.4: 15, 17, 22, 25, 28, 35, 36, 39, 47, 63;
Homework Problems (to be collected)       Section 5.1: 44;        Section 5.2: 28, 31, 32;        Section 5.3: 35,        Section 5.4: 35;

Homework 7, ,    due November 3,     Friday, before class:
Warm up problems: nbsp;      Section 6.1: 1, 2, 3, 4, 6, 7.                  Section 6.2: 1, 3.                  Section 7.1: 1, 3, 8
Extra problems:            Section 6.1: 15, 16, 17, 18, 19, 20, 23, 29, 31, 34, 37, 40, 46, 50;            Section 6.2: 5, 6, 11, 17, 19, 22, 25, 26, 32, 34, 36,            Section 7.1: 15, 16, 19, 21, 23, 24, 32. Homework Problems (to be collected)       Section 6.1: 16, 23        Section 6.2: 6, 17        Section 7.1: 19, 22

Homework 8, ,    due November 15,     Wednesday, before class:
Warm up problems: nbsp;      Section 7.2: 2, 4, 5, 7, 8, 10, 14;                  Section 7.3: 3, 5, 6;                  Section 8.1: 4, 5, 6, 7;
Extra problems:            Section 7.2: 21, 22, 23, 25, 27, 29, 31, 32, 36, 37, 39, 48;            Section 7.3: 7, 9, 14, 19, 28, 30, 34, 38, 43, 44, 49;            Section 8.1: 14, 17, 24, 26, 27, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39; 40, 42. Homework Problems (to be collected)       Section 7.2: 23, 40        Section 7.3: 7, 38        Section 8.1: 26, 31 [hint: read the proof of the 5-color thm],

Homework 9,     due December 1,     Friday, before class:
Warm up problems:        Section 8.2: 1, 2, 6, 7;                  Section 8.3: 3, 8, 9;                  9.1: 11;
Extra problems:            Section 8.2: 13, 14, 22, 23, 25.            Section 8.3: 13, 15, 24, 25, 26;           Section 9.1: 19, 30, 35, 39, 40, 41, 46, 47, 48, 50, 55;
Homework Problems (to be collected)       Section 8.1: 27;        Section 8.2: 23, 31;        Section 8.3: 25;        Section 9.1: 41, 48,

Homework 10,     due December 11,     Monday, before class: [NO LATE homework is accepted. This HW won't be returned graded before January, if wanted to be graded, then submit by Friday Dec 8 before class]
Warm up problems:        Section 9.2: 1, 3, 4, 5, 6.        Section 9.3: 2, 3, 6.       Section 10.1: 1.       Section 10.2: 5.       Section 10.3: 1.       Section 11.1: 4.       Section 14.3: 1,       Section 13.1: 2, 3, 5.       Section 13.2: 4.
Extra problems:            Section 9.2: 8, 11, 12, 15.           Section 9.3: 7, 10, 12, 17, 23, 27.           Section 10.2: 10, 12, 16, 20, 27, 32, 33.           Section 10.3: 14.           Section 11.1: 6, 8, 13, 17.           Section 14.1: 27, 28           Section 14.2: 1, 2, 10, 12,           Section 14.3: 14, 17,           Section 13.1: 10,           Section 13.2: 10.           Section 12.1: 13, 14, 15.

Homework Problems (to be collected [do five out of 7]):        Section 9.2: 11 - 12 [one problem].       Section 9.3: 23;        Section 10.2: 34;        Section 11.1: 14;        Section 14.2: 14;        Section 13.2: 10;        Section 12.2: 36;

HOMEWORK: FALL 2016:

From each homework assigments solve five out of the six to be collected problems. The solutions should include proofs, should be readable and as self-complete as possible.

Homework 1 ,    due September 7,    Wednesday, before class:
Warm up problems:       Section 1.1: 4, 5, 7, 11, 12.                  Section 1.2: 1, 2, 3, 4, 5, 6, 10.        Section 1.3: 1, 3, 4, 7.
Extra problems:            Section 1.1: 18, 25, 27, 28, 34, 35, 36, 39, 40, 41.        Section 1.2: 11, 12, 14, 15, 17, 28, 36.        Section 1.3: 17, 26, 27, 28, 30, 33.
Homework Problems (to be collected)       Section 1.1: 33, 39;        Section 1.2: 14, 31,        Section 1.3: 17, 29.

Homework 2 ,    due September 14,    Wednesday, before class:
Warm up problems:       Section 2.1: 1, 2, 4, 8.                  Section 2.1: 1, 2, 3, 7, 8, 9.
Extra problems:            Section 2.1: 12, 17, 18, 19, 20, 22, 23, 24, 25, 31, 36, 37, 43, 48, 52, 61, 63, 66, 69        Section 2.2: 12, 24, 26, 29, 30, 31, 32, 34, 35, 37.
Homework Problems (to be collected)       Section 2.1: 20, 51, 55;        Section 2.2: 26, 32, 37.

Homework 3 ,    due September 21,    Wednesday, before class:
Warm up problems:       Section 2.3: 1, 2, 3, 4.                  Section 3.1: 1, 2, 3, 4, 7.
Extra problems:            Section 2.3: 9, 13.        Section 3.1: 10, 13, 15, 16, 20.
Homework Problems (to be collected) SUBMIT ONLY 5 out of 6!!!       Section 2.2: 30.        Section 2.3: 8        Section 3.1: 8, 16, 26, 38.

Homework 4 ,    due September 28,    Wednesday, before class:
Warm up problems:       Section 3.2: 2, 3, 4, 6, 7.                  Section 3.3: 1, 2, 4, 7.
Extra problems:            Section 3.2: 17, 18, 20, 22, 24, 25, 29, 30, 31, 34, 36, 37, 40, 43, 45, 46.        Section 3.3: 15, 17, 20, 23, 24, 25, 26, 31, 34, 39, 43.
Homework Problems (to be collected) SUBMIT ONLY 5 out of 6!!!       Section 3.2: 14, 36, 41, 44        Section 3.3: 22, 30.

Homework 5 ,    due October 5,    Wednesday, before class:
Warm up problems:       Section 3.4: 1, 2, 3.                  Section 4.1: 1, 2, 3, 5, 9, 10, 12.
Extra problems:            Section 3.4: 8, 9, 10, 11, 16, 18, 23, 26, 27, 29, 32.        Section 4.1: 16, 17, 20, 21, 23, 22, 24, 28, 29, 31, 33, 43, 44, 45.
Homework Problems (to be collected) SUBMIT ONLY 5 out of 6!!!       Section 3.4: 10, 18, 34;        4.1: 22, 45, 56.

Homework 6 ,    due October 12,    Wednesday, before class:
Warm up problems:               Section 4.2: 2, 3, 5;        Section 4.3: 3, 8;        Section 5.1: 14;        Section 5.2: 1, 6, 7;
Extra problems:               Section 4.2: 9. 10, 15, 18, 22, 25, 26;               Section 4.3: 9, 15;               Section 5.1: 32, 35, 47;               Section 5.2: 9, 10, 11, 13, 22, 29, 34;
Homework Problems (to be collected)        Section 4.2: 16, 21;        Section 5.1: 24;        Section 5.2: 11, 25, 31;

Homework 7 ,    due October 26,    Wednesday, before class:
Warm up problems:               Section 5.3: 3, 4;        Section 5.4: 1, 2, 6;        Section 6.1: 2, 3, 5, 6, 7, 8;        Section 6.2: 1, 3;
Extra problems:               Section 5.3: 22, 23, 25, 32, 33, 34, 35, 39, 40;               Section 5.4: 15, 18, 25, 28, 30, 35, 37, 40;               Section 6.1: 13, 18, 19, 20, 21, 27, 31, 33, 39, 47, 48;               Section 6.2: 13, 15, 17, 20, 25, 31, 35, 36, 40.
Homework Problems (to be collected)        Section 5.3: 33-34 counted as one problem;        Section 5.4: 30;      &nbsp; Section 6.1: 13, 22, 34;        Section 6.2: 36;

Homework 8 ,    due November 2,    Wednesday, before class:
Warm up problems:              Section 7.1: 1, 3, 8;        Section 7.2: 2, 4, 5, 7, 8, 10, 14;
Extra problems:               Section 7.1: 15, 16, 19, 20, 21, 23, 25, 31, 34.        Section 7.2: 21, 22, 25, 29, 31, 36, 38, 48;
Homework Problems (to be collected)       Section 7.1: 16, 21, 25;        Section 7.2: 23, 32, 36, ;

Homework 9 ,    due November 14,    Monday, before class:
Warm up problems:              Section 7.3: 3, 4, 5;        Section 8.1: 4, 5, 6, 7;
Extra problems:               Section 7.3: 7, 9, 14, 20, 21, 29, 30, 33, 36, 43, 44, 48;        Section 8.1: 14, 15, 20, 29, 33, 37,38, 39; 40. 41, 44.
Homework Problems (to be collected)       Section 7.3: 33, 38, 48 ;        Section 8.1: 32, 33, 37 ;

Homework 10 ,    due November 30,    Wednesday, before class [no late hw is accepted!]:
Warm up problems:              Section 8.2: 1, 2, 6, 7;        Section 8.3: 3, 8, 9;        Section 9.1: 2–11.        Section 9.2: 1, 3, 4, 5, 6.
Extra problems:        Section 8.2: 13, 14, 22, 23, 25.        Section 8.3: 16, 22, 23, 24.        Section 9.1: 19, 30, 36, 37, 39, 40, 41, 46, 56.        Section 9.2: 8, 11, 12, 14.
Homework Problems (to be collected)       Section 8.2: 22. ;        Section 8.3: 24.;        Section 9.1: 41-42 as one problem, 49,       Section 9.2: 11, 14.

Homework 11 ,    due December 9, Friday, in mailbox, by noon;[no late hw is accepted!]:
Warm up problems:              Section 9.3: 2, 3, 6.        Section 10.1: 1.        Section 10.2: 5.        Section 10.3: 1.        Section 11.1: 4.        Section 14.3: 1,        Section 13.1: 2, 3, 5.        Section 13.2: 4.
Extra problems:        Section 9.3: 8, 10, 11, 18, 19, 20, 24, 27.        Section 10.2: 10, 12, 19, 20, 29, 31, 33.        Section 10.3: 2, 4, 7, 8, 12, 14.        Section 11.1: 5, 8, 13, 17, 30.        Section 14.1: 27        Section 14.2: 1, 2, 10, 12,        Section 14.3: 14, 16,        Section 13.1: 10,        Section 13.2: 6.        Section 12.1: 13, 14, 15.
Homework Problems: Do 4 out of 6! (to be collected)       Section 9.3: 24;       Section 10.2: 29;       Section 11.1: 13;        Section 14.2: 14;        Section 13.2: 9;        Section 12.2: 37;

Homework is usually due on Wednesdays, with solutions distributed on Fridays. Start early on homework assignments, and ask questions if anything is unclear or if you need guidance. I can provide a push in the right direction when people get stuck. The purpose of the homework is to help students understand the ideas, so it is okay to toss around some thoughts with others. Be sure to write up solutions on your own. Solutions should include full justifications in sentences.
The text and class cover classical examples, and working other problems for homework leads to deeper understanding. I try to cover by Friday almost all of what is needed to do the homework for the next week; sometimes there will be an item or two left for Monday.
I hold voluntary collaborative study sessions on Monday 3:00-3:50pm. Students discuss the homework in small groups; I listen and answer questions. Whether you attend or not, you should still try to solve the problems before Monday. The Monday discussion is more beneficial if you have already tried the problems.
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. The test problems are chosen among the recommended problems.

THESE HOMEWORK BELOW IS FROM THE PREVIOUS YEARS (and link might not work anymore)!!!!!!!!!!!!!!!!!!

• Homework 1: DUE:  Sept 9 (Wednesday), before class

• Homework 2: DUE:  Sept 16 (Wednesday), before class

• Homework 3: DUE:  Sept 23 (Wednesday), before class

• Homework 4: DUE:  Sept 30 (Wednesday), before class

• Homework 5: DUE:  Oct 7 (Wednesday), before class

• Homework 6 DUE:  Oct 21 (Wednesday), before class

• Homework 7 DUE:  Oct 28 (Wednesday), before class

• Homework 8 DUE:  Nov 4 (Wednesday), before class

typo in #6, should be i<= n/2!
• Homework 9 DUE:  Nov 11 (Wednesday), before class

• Homework 10 DUE:  Nov 18 (Wednesday), before class

• Homework 11 DUE:  Dec 2 (Wednesday), before class

• Homework 12 DUE:  Dec 14 (Monday), before 3 pm, Do 5 from the list
NO LATE HOMEWORK IS ACCEPTED!!!
Note the typo in 1.b: m_ should be t_

• Homework 1: DUE:  Sept 5 (Friday), before class

Problem Session: Wednesday 2:00-2:50pm Illini Hall 1

• Homework 2: DUE:  Sept 17 (Wednesday), before class

• Homework 3: DUE:  Sept 24 (Wednesday), before class

• Homework 4: DUE:  October 1 (Wednesday), before class

• Homework 5: DUE:  October 8 (Wednesday), before class

• Homework 6: DUE:  October 15 (Wednesday), before class

• Homework 7: DUE:  October 29 (Wednesday), before class

• Homework 8: DUE:  November 5 (Wednesday), before class

• Homework 9: DUE:  November 12 (Wednesday), before class

• Homework 10: DUE:  November 19 (Wednesday), before class

• Homework 11: DUE:  December 3 (Wednesday), before class

• Homework 12: DUE:  Dec 12 (Friday) noon, via e-mail, strict deadline, no late hw is allowed!
Do 5 problems!
Do at least 2 out of the next 5 problems:
Problem 1. Prove that every balanced partition of the half graph into 2k classes contains at least k/100 not epsilon-regular pairs, where every partition class is fully contained in one of the classes of the half-graph. Note: The half graph has n vertices in each classes. Note that k is much larger than 1/epsilon, and n is much larger than k.
Chapter 14.2: 7: Let G be an n-vertex graph having a proper coloring such that every vertex has neighbors in at most k color classes. Prove that the independence number is at least n/(k + 1). Chapter 14.2: 10 14.3: 14, 22.
Do at least one from Chapter 12: 12.1.15; 12.2.37
Do at least one from Chapter 13: 13.1.10; 13.2.6.

• Homework 1: DUE:  Sept 7 (Friday)
WARM UP PROBLEMS: Section 1.1: 3, 4, 5, 7, 8, 11, 12, 14; Section 1.2: 1, 2, 4, 6, 8, 10; Section 1.3: 1, 3, 4, 5. Do not write up. These problems are easier or shorter to check understanding.
EXTRA PROBLEMS: Section 1.1: 19, 22, 26, 27, 29, 32, 34, 37; Section 1.2: 11, 13, 14, 25, 26, 28, 33, 35, 38, 41, 42, 45, 48, 49, 52.
WRITTEN PROBBLEMS: Do five of the six problems. Type your solution. Prove your statements.
Section 1.1: 34; 37; Section 1.2: 16 (a),(b),(d), 19; Section 1.3: 16, 27;

• Homework 2: DUE:  Sept 12 (Wednesday)

• Homework 3: DUE:  Sept 19 (Wednesday)  From Problem 2 submit only part (b)!

• Homework 4: DUE:  Sept 26 (Wednesday)

• Homework 5: DUE:  Oct 5 (Friday)

• Homework 6: DUE:  Oct 15 (Monday) [NOT WEDNESDAY!!!!!]
WARM UP PROBLEMS: Section 4.2: 2, 3, 5. Section 4.3: 3, 8.
EXTRA PROBLEMS: Section 4.2: 8, 10, 15, 21, 25. Section 4.3: 9, 15.
WRITTEN PROBBLEMS: Section 4.2: (do both) 16, 21. and several others...

• Homework 7: DUE:  Oct 29 (Monday)
WARM UP PROBLEMS:
Section 6.1: 2,3,4,6,7,8;
Section 6.2: 1,3;
Section 7.1: 1,2,3,4
EXTRA PROBLEMS:
Section 6.1: 11, 13, 16,17, 20, 25, 29, 30, 31, 35, 38, 39;
Section 6.2: 4,5, 11, 12, 16, 22, 24, 31, 35;
Section 7.1: 16, 17, 18, 20, 21, 29, 31, 33.
WRITTEN PROBBLEMS:
Section 6.1: 21, 24, 30;
Section 6.2: 18, 37;
Section 7.1: 25;

• Homework 8: DUE:  Nov 5 (Monday)
WARM UP PROBLEMS:
Section 7.2: 2,4, 6, 7, 8, 10, 14;
Section 7.3: 3,4, 5
EXTRA PROBLEMS:
Section 7.2: 21, 22, 25, 29, 30, 36, 38;
Section 7.3: 7, 9, 14, 17, 21, 26, 29, 30, 31, 43.
WRITTEN PROBBLEMS:
Section 7.1: 21;
Section 7.2: 37, 47
Section 7.3: 6, 29;
Section 8.1: 24

• Homework 9: DUE:  Nov 9 (Friday)
WARM UP PROBLEMS:
Section 8.1: 1, 4, 5, 6, 7;
Section 8.2: 1, 3, 6, 7;
Section 8.3: 3, 4, 6, 7;
EXTRA PROBLEMS:
Section 8.1: 11, 15, 20, 26, 31, 33, 37, 41;
Section 8.2: 12, 14, 15, 21, 25, 28, 39, 40, 43;
Section 8.3: 10, 13, 18, 25, 34, 42, 50;
WRITTEN PROBBLEMS:
Section 8.1: 44; TYPO IN part (b), the "at most" should be "at least"
Section 8.2: 21, (27,28 as one problem), 39
Section 8.3: 22, 24;

• Homework 10: DUE:  Nov 16 (Friday)

• Homework 11: DUE:  Nov 28 (Wednesday)

• Homework 12: DUE:  Dec 17 (Monday) noon, via e-mail, strict deadline, no late hw is allowed!
Do 5 problems!
Do at least 2 out of the next 5 problems:
Problem 1. Prove that every balanced partition of the half graph into 2k classes contains at least k/100 not epsilon-regular pairs, where every partition class is fully contained in one of the classes of the half-graph. Note: The half graph has n vertices in each classes. Note that k is much larger than 1/epsilon, and n is much larger than k.
Chapter 14.2: 5, 9; 14.3: 14, Note there is a typo in part (b), it should be R(k,k), 22.
Do at least one from Chapter 12: 12.1.15; 12.2.37
Do at least one from Chapter 13: 13.1.9; 13.2.6.

Advice for students in Math 580 / CS 571:

General: I hope you will enjoy the variety and beauty of the combinatorial problems discussed in this course. The course provides a fairly thorough study of basic combinatorial techniques at the graduate level, plus an introduction to some additional topics.

Background: The course is an introduction, but at the graduate level. It assumes `mathematical maturity'', which means familiarity with elementary undergraduate mathematics and a level of comfort with reading and writing proofs. There is no specific prerequisite in combinatorics; I will develop all the combinatorics from the beginning. However, {\it the course moves quickly and covers a lot}. Some students will have had previous exposure to enumeration or graph theory. What matters more than specific background is interest in the material and a commitment to work hard.

Feedback: Please feel free to offer feedback by email or in office hour about the lectures, text, topics, homework, etc. Also feel free to ask questions in class. I will use email to make announcements about the course (including clarification of items from class), and email is often the easiest and quickest way to reach me. When I hear about items that are unclear or in error (including on homeworks), I can send everyone email to fix it.

Homework Solutions:
You may be sure, dear Crito, that inaccurate language is not only in itself a mistake: it implants evil in men's souls. --- Socrates, in Plato's Phaedo.
From past experience, I know that some(?) (ALL!) of you will need to improve your writing. An important part of doing mathematics is communicating it clearly. I suggest the following. Instead of solving all the problems first and then writing them up, write up problems right away when you solve them. You then have a chance to forget what you wrote for the first few problems while you work on the others. At the end, before submitting the homework, read what you wrote earlier. If you find it hard to follow, then graders will find it even harder! At this point revise your exposition so that it really say what you had in mind.
When you think of a proof and write it down, it seems clear to you because the ideas are fresh in your mind. Revising after you have a chance to forget the thoughts is very important and is the only way you can be confident that what you wrote expresses what you meant. This process also helps you discover habits of expression that make your exposition unclear, and then your early drafts of future work will be better. Writing as you solve gives some benefits of the revision process without taking too much extra time and without requiring you to solve all the problems by Saturday. Some of you like professor West's opinion on correct grammar and usage in mathematical writing are posted at https://math.uiuc.edu/\~west/grammar.html.
There is much of beauty in combinatorics, so there is much I want to tell you. The lectures aim to increase your interest in these topics and to convey a basic understanding of the techniques and proofs and how they fit together. Sometimes you may not fully understand all details just by attending lecture; that's why the details are in the text. The lectures are a guide to the text. Using your notes to indicate the important points, review the text to understand the details securely (also ask questions if something is not adequately explained!) Mastery of the material comes from reflecting on it at your own pace and from solving problems, which is why the homework is so important. If you are struggling with the material, I will be happy to give further explanations. Don't give up without at least trying to get some help or clarification. I hope you all have a great time and learn a lot!