CSE 591 / MATH 591 Combinatorial Design Theory
Contact Information:
I am located in Brickyard 444.
Contact me by email at Charles.Colbourn@asu.edu as the most reliable way to reach me.
My office hours are Tuesdays 10:30-11:20, Fridays 10:00-11:00.
The class schedule is T Th 9:00-10:15.
The room is BYAC 260.
Background in discrete mathematics, linear algebra, and algebra is assumed.
Previous courses in combinatorics and graph theory will be useful but are not required.
We will work through the majority of the text Combinatorial Designs: Constructions and Analysis
by Douglas R. Stinson (Springer, 2004).
Combinatorial design theory had its origins in finite geometry, algebra, and number theory.
About a century ago, it coalesced as a field around applications in experimental design.
Soon after, it became central in the evolving area of error-correcting codes for communication.
Since that time, it has continued to develop deep and elegant connections with classical mathematics, while developing more and more applications.
A prototypical problem is the following. You are buying tickets for the lottery.
Each ticket is a selection of 6 numbers from a set of 49 numbers.
Then 6 numbers are chosen by some unpredictable process.
If one of your tickets shares at least 3 numbers with those chosen, you're a winner.
How many tickets do you need to buy to make sure that you're a winner?
Here's another. You are trying to assign v faculty members to committees. Every committee has exactly five members.
For what values of v is it possible to make an assignment so that every two faculty members serve on exactly one committee together?
Another was discussed in the first class: See https://www.usenix.org/conference/atc13/technical-sessions/presentation/cidon
"Copysets: Reducing the Frequency of Data Loss in Cloud Storage".
Assessment:
- 10 homeworks, one each week for the first ten weeks -- 4% each.
They are due at the start of class every Thursday.
Homework 1 is due on 23 January.
Homework 2 is due on 30 January.
Homework 3 is due on 06 February.
Homework 4 is due on 13 February.
Homework 5 is due on 20 February.
Homework 6 is due on 27 February.
Homework 7 is due on 27 March.
Homework 8 is due on 03 April.
Homework 9 is due on 10 April.
Homework 10 is due on 17 April.
- a project counting 60%.
It is due on 08 May at 9:20 a.m.
It is to be emailed to colbourn@asu.edu by this time.
The main features are:
- the topic is different for each individual, and is chosen by the
student. Particular project topics should be discussed with me to ensure
that they are reasonable.
- Projects are intended to be a more focussed exploration of topics beyond the
regular lecture material.
- Due date is at the final exam time for the course.
Start on the project early!
- Feel free to consult anyone, especially me, about the project as you
work on it.
- The most important thing that I want to see in the projects is a
creative and innovative approach that clearly demonstrates a deep understanding
of some topic relevant to the course. In general, depth is preferred to
breadth, and your ideas are preferred to someone else's.
- No tests or examinations are planned.