[Discrete-math-seminar] Wed Feb 28, 11am seminar, Robert Ellis

[Robert Ellis]

Please join us Wednesday for the combinatorics research seminar at 11am in 
E1 241.  I will continue the problem below in adaptive coding theory, 
presenting a theorem of Spencer and Winkler for when the number of balls 
goes to infinity.  An important open problem for the dual case will be 
discussed.

Wednesday Feb 28 Talk
======================
Speaker: Robert Ellis (IIT Applied Mathematics)
Title: Three balls on a cliff, part 2
Time: 11:00am
Location: E1 241

Abstract: Three balls are placed on a cliff at distance k from the edge. Two 
players, Paul and Carole, play the following q-round game.  Each round, Paul 
splits the balls into two subsets.  Then Carole chooses one of the subsets and 
moves each ball in it one step closer to the cliff (at position 0 a ball falls 
off).  We discuss winning strategies for q-round games with the following 
goals.

1) Paul wins if after q rounds at most 1 ball remains on the cliff.
2) Paul wins if after q rounds at least 1 ball remains on the cliff.

In general, we can consider n balls instead of 3.

The first goal corresponds to an adaptive error-correcting code of very high 
radius, and the second to an adaptive covering code of very high radius.  We 
present exact formulas for some small cases.

We will discuss what questions are open and also some results of Spencer and 
Winkler when n, k, q all go to infinity, but k is a fraction of q (i.e., high 
radius adaptive codes).