REGS in Combinatorics - University of Illinois

Organized by Douglas B. West

"REGS" stands for "Research Experiences for Graduate Students". The Mathematics Department of the University of Illinois (Urbana) has run this program each summer since 2004. In most research areas, the program consists of projects for one or two students, but in combinatorics the program is quite different.

The Combinatorics REGS group is a lively collaborative research group in which many problems are proposed and students coalesce into groups to work on those that appeal to them. Many joint papers have emerged. We meet MWF afternoons for about 2.5 hours each during Summer Term II. Presented by both faculty and students, the come from conferences, web pages, journal articles, etc.

The limited is restricted to students in our Math Department who have finished at most two years of graduate study. The program is designed to provide an early exposure to research, thereby increasing mathematical maturity and easing the transition from coursework to research. Projects may or may not lead to thesis research.

More senior students participate in the combinatorics group without direct funding from REGS, since they continue to find it valuable. The mix of discussion among students with various backgrounds and various levels of experience contributes to the training of all the students.
Reports from early years: 2006: ps, pdf; 2005: ps, pdf; 2004: ps, pdf.

Selected Problems presented in the Combinatorics REGS

Note: basic terminology omitted from individual problem descriptions appears in the Glossary.

Problems presented in Summer 2008

  1. Szymanski's Conjecture
  2. Routing permutations via matchings
  3. Monotone sequence games
  4. Sum-choosability
  5. Eternal domination number
  6. Non-separating trees in cohesive graphs
  7. Folkman's bound on chromatic number
  8. Spanning cycles in defective hypercubes
  9. Monochromatic quasiprogressions
  10. Buratti's Conjecture
  11. Toughness and spanning cycles
  12. Thomassen's vertex partition problem
  13. A consequence of Hadwiger's Conjecture
  14. Nonrepetitive colorings
  15. Induced acyclic subgraphs of planar digraphs
  16. Crease patterns and paper folding
  17. Rainbow connectedness
  18. Turán's Theorem with colors
  1. Irregularity strength of digraphs
  2. Packing degree lists
  3. Pinwheel scheduling
  4. k-connected orientations
  5. Choosability with separated lists
  6. Mindegree of Ramsey-minimal graphs
  7. Domination in cubic graphs
  8. Domination and bipartite subgraphs
  9. Kneser representations
  10. Binary subtrees with few path labels
  11. Star coloring of graphs
  12. Totally greedy coin sets
  13. Cycle spectra of Hamiltonian graphs
  14. c-nearly regular subgraphs
  15. Vertex arboricity and planar graphs
  16. Arboricity ratio
  17. Poset dimension and chromatic number
  18. Sorting pairs in bins
The Louisville group has prepared pdfs of their problems: Summary 1, Summary 2, Summary 3

Selected problems presented in Summer 2007

There were almost 40 problems presented in Summer 2007; some are gradually being converted into html to be posted here.
  1. S(2), Ryser, and Brualdi Conjectures
  2. Hub number
  3. Path factorization of circulant digraphs
  4. Repetition number
  5. Splitting digraphs
  6. Hendry's Conjecture
  7. The 1,2,3-Conjecture and the 1,2-Conjecture
  8. The Caccetta-Häggkvist Conjecture
  9. Injective chromatic number
  1. 4-ordered planar Hamiltonian graphs
  2. Group flows and group connectedness
  3. Acquisition and game-acquisition in graphs
  4. Second Hamiltonian cycles
  5. Thickness of sphere-of-influence graphs
  6. On-line Ramsey games
  7. Cop number