REGS in Combinatorics - Univ. of Illinois

Organized by Douglas B. West

"REGS" means "Research Experiences for Graduate Students", formally since 2004. In most research areas, this program in the U. Illinois Math Department consists of projects for one or two students, but the combinatorics program is quite different. The Combinatorics REGS group is a lively collaborative research group where many problems are proposed and students work in groups on those that interest them. Many joint papers have emerged. We meet MWF afternoons for about three hours. Presented by both faculty and students, the problems come from conferences, web pages, journal articles, etc.

Funding is mostly 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 and exposition, thereby increasing mathematical maturity and easing the transition from coursework to research. Projects may or may not lead to thesis research.

More senior students and computer science students also participate in the combinatorics group without direct funding from REGS since they find it valuable. Discussion among students with various backgrounds and various levels of experience contributes to the training of all the students. As of 2009, the program also includes entering graduate students, and we aim to involve more visiting faculty.

Reports from early years: 2006: ps, pdf; 2005: ps, pdf; 2004: ps, pdf.

Selected Problems from the Combinatorics REGS

Note: Additional basic terminology appears in the Glossary.

Problems presented in Summer 2009

  1. Tree-thickness and girth
  2. Rainbow matchings
  3. Boxicity and maximum degree
  4. Maker-breaker games
  5. Bichromatic number
  6. Covering numbers & hypergraph transversals
  7. k-majority digraphs
  8. Proper weightings and lucky labelings
  9. Pentagulated graphs
  10. Saturation numbers of graphs
  11. Some conjectures of Graffiti.pc
  1. Complementary cycles in multipartite tournaments
  2. Variations on Chvátal's Conjecture
  3. Induced lines in metric spaces
  4. Cycles from block permutations
  5. Spanning paths in Fibonacci-sum graphs
  6. Edge-graceful labelings
  7. The domination game
  8. Degree-splittability
  9. Acute weak triangulations
  10. Ryser, Jones, and Tuza Conjectures
  11. Arborally satisfied point sets
  12. Monotone Sequence Games II
The Louisville group has prepared pdfs of their problems: Summary 1

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. Kézdy-Snevily, 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