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.

A more detailed description appears in the proposal for the 2010 program (ps, pdf).
Reports on results and activities from earlier years: 2009: ps, pdf; 2007: ps, pdf; 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
  12. Complementary cycles in multipartite tournaments
  13. Variations on Chvátal's Conjecture
  14. Induced lines in metric spaces
  15. Cycles from block permutations
  16. Spanning paths in Fibonacci-sum graphs
  17. Edge-graceful labelings
  18. The domination game
  19. Degree-splittability
  20. Acute weak triangulations
  21. Ryser, Jones, and Tuza Conjectures
  1. Arborally satisfied point sets
  2. Monotone sequence games II
  3. Density version of Turán's Theorem
  4. Complexity of Combinatorial Nullstellensatz
  5. A covering problem on trees
  6. Stack and queue layouts
  7. Dynamic coloring
  8. On-line coloring of [unit] interval graphs
  9. Spanning trees in 3-regular graphs
  10. Diameter of edge-transitive 3-regular graphs
  11. Two problems on de Bruijn cycles
  12. Splits of coverings
  13. Large P-free families of sets
  14. Partition regularity of Pythagorean triples
  15. Erdős-Hajnal Conjecture on homogeneous number
  16. Forest leaves from cycle systems
  17. Laborde-Payan-Xuong Conjecture
  18. König-Egerváry graphs
  19. Removable edges in k-connected graphs
  20. Coloring of mixed hypergraphs
The Louisville group has prepared pdfs of their problems: Summary 1, Summary 2

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