REGS in Combinatorics - Univ. of Illinois

Organized by Douglas B. West

"REGS" means "Research Experiences for Graduate Students". The Combinatorics REGS program has existed every summer since 2004. Much larger than Illinois Math REGS programs in other topics, it is a lively collaborative research group where many problems are proposed and students work in groups on the problems that interest them. Presented by both faculty and students, the problems come from conferences, web pages, journal articles, etc. We meet MWF 10:30-12 and 2-5 (more intensively during the first week). The program provides an early exposure to research and exposition, thereby increasing mathematical maturity and easing the transition from coursework to research. Many joint papers have emerged. Projects may or may not lead to thesis research.

Funding is mostly restricted to entering students in our Math Department and those who have finished 1-2 years of graduate study. More advanced students, computer science students, and other visitors also participate in the combinatorics group without direct funding from REGS. Discussion among students with various backgrounds and various levels of experience contributes to the training of all the students. Some visiting faculty also participate. Further information appears in the 2010 proposal (ps, pdf) and yearly reports: 2011; 2010; 2009; 2007; 2006; 2005; 2004.

Note on viewing Mathjax: During summer 2011, we switched to using Mathjax to display notation on the problem pages (most of the later pages are in Mathjax). This makes pages easier to create (notation is typed in equation mode of TeX between "$ $" or "$$ $$"). Also, TeX can produce some arrangements (like binomial coefficients) that html cannot. When browsing a page in Mathjax, there is a slight delay while the display of notation is computed. The appearance can be refined by right-clicking on a piece of notation and exploring; changes to settings should persist.

Note on producing pages with Mathjax: Mathjax does not recognize TeX font commands for text or layout; continue to use html commands to italicize, make tables, etc. Also, html will swallow input after "<"; use "\lt" for "less than" and "\gt" for "greater than" in notation.

Problems presented in Summer 2011

The RESULTS PAGE lists results obtained in REGS toward or related to the problems proposed. For basic terminology not given on problem pages, see the Glossary.
  1. Game matching number
  2. (p,q)-splits of (0,1)-matrices
  3. Mean size of subtrees of a tree
  4. Edge-achromatic number of Kn
  5. Cops locating a robber
  6. Number of chains in width-2 posets
  7. k-corners in subsets of d-dimensional grids
  8. Chromatic number of tournaments
  9. Track number of line graphs
  10. Visibility number of hypercubes
  11. Ranking and list ranking of graphs
  12. t-tone colorings
  13. Accessibility of the Fibonacci sequence
  14. Symmetry dynamics
  15. Coloring of tangency graphs of cuboids
  16. Homothetic Ramsey problems on grids
  17. Revolutionaries and spies, revisited
  18. Paintability
  19. Stack-sortability
  20. Monochromatic empty triangles
  21. Art Gallery problems
  22. Counting k-paths in transitive tournaments
  23. Stable covert networks
  24. List distinguishing number of graphs
  25. Monosources vs. rainbow cycles
  1. Expectancy of σ in τ-avoiding permutations
  2. Colorful paths in colored graphs
  3. Cycle-complete Ramsey numbers
  4. Macdonald's Identity for reduced words
  5. Coloring of fractional powers of graphs
  6. Games built on chip-firing (Chaos)
  7. The upper matching conjecture
  8. Universal words for subpermutations
  9. Extension of matchings to spanning cycles in hypercubes
  10. Unimodality of the independent set sequence
  11. Acyclic digraphs with many linear extensions
  12. Total weight choosability
  13. Embedding planar Laman graphs on grids
  14. Precoloring list extension for planar graphs
  15. Game nonrepetitive coloring
  16. Chromatic number of triangle-free graphs
  17. The F-saturation game and Game saturation number
  18. The Equal Union Property
  19. Equivalence coverings of cycle-powers
  20. MST for point-sets in the unit square
  21. Concavity of mixed van der Waerden numbers
  22. Arrangements of n lines in the plane
  23. Properties of co-spectral graphs
  24. Extensions of biclique decomposition
  25. Decomposition of 5-regular graphs (SOLVED)
  26. Isomorphic decomposition into strongly regular graphs

Problems presented in Summer 2010

The RESULTS PAGE lists some of the results obtained in REGS toward or related to the problems proposed.
  1. Mixed Ramsey theory
  2. Consequences of the Berge-Fulkerson Conjecture
  3. Largest graphs having p perfect matchings
  4. Realizing degree lists with few perfect matchings
  5. Total bar visibility number
  6. On-line Chain-Partitioning for Semiorders
  7. Tournaments and generalized score sequences
  8. Lines tangent to four unit balls
  9. Fractional dimension of posets
  10. 2-domination and annihilation number
  11. Universal cycles for permutations (stub)
  12. Coloring a graph with no H-minor
  13. b-coloring in regular graphs
  14. Reconstruction of posets from ideal sizes
  15. 3-cordial colorings
  16. Yao's table storage problem
  17. Star-critical Ramsey numbers
  18. Ehrenfeucht-Fraissé game & subgraph isomorphs
  19. Edge-antipodal colorings of hypercubes
  20. Segment orders
  21. Immersion order on graphs
  22. Sorting by k-ary comparisons
  23. Circumference of claw-free graphs
  24. Revolutionaries and spies
  25. Monotone Hamiltonian paths in hypercubes
  26. Undirected edge geography (stub)
  27. Dynamic coloring
  1. Erdős-Ko-Rado problem for graphs
  2. Linear and weak discrepancy in posets
  3. Disjoint maximal independent sets (stub)
  4. Edge-reconstruction of multigraphs
  5. Matching in geometric graphs (SOLVED)
  6. Expandable L(2,1)-labelings
  7. Crossings in horizontal drawings
  8. Group connectivity of graphs
  9. Nowhere-zero solutions to linear equations
  10. Chaos: toppling piles of tokens
  11. Difference graphs
  12. Implications between linkage properties
  13. Trail-ordered and circuit-ordered graphs (stub)
  14. Spatial embeddings of graphs
  15. Grab the Gold! - A tree-eating game
  16. Maker-Breaker games on grids
  17. Havel-Hakimi residue and independent sets
  18. Quack number
  19. F-saturated k-graphs
  20. Chromatic number vs. clique number
  21. Sorting by 3-branches
  22. Turán problems for co-degree
  23. A generalization of proper edge-coloring
  24. Acyclic orientation game
  25. Monophilic graphs
  26. Coloring the square of the Kneser graph (stub)
The Louisville group prepared pdf writeups of 16 problems in a single file. A few of these problems also appear above.

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 appear 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