Combinatorial Mathematics, Fall 2015

**Instructor:** Jozsef Balogh

**Office:** 233B Illini Hall

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

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

**Time and place:** 11:00- 11:50pm MWF, Altgeld Hall 347

**Problem Session: ** Monday 2:30-3:30pm Altgeld Hall 345

**Office Hour:** by appointment, designated time: Wednesday, Friday 2:00-2:50pm

**Make up:**

**Midterm exam: 168 Everitt on Monday, October 12, 2015 from 5-6:30 pm
covering Chapters 1--4**

**Final exam: ** December

**Make up class:**

typo in #6, should be i<= n/2!

NO LATE HOMEWORK IS ACCEPTED!!!

Note the typo in 1.b: m_ should be t_

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.

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 2:00-3:50pm. Students discuss the homework in small groups; I listen and answer questions (from 2:30-3:30). Whether you attend or not,

Homework allows you to choose

THESE HOMEWORK BELOW IS FROM THE PREVIOUS YEARS!!!!!!!!!!!!!!!!!!

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.

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.

Section 1.1: 34; 37; Section 1.2: 16 (a),(b),(d), 19; Section 1.3: 16, 27;

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...

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;

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

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;

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.

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!