REGS in Combinatorics - Univ. of Illinois

Organized by Douglas B. West

"REGS" means "Research Experiences for Graduate Students". The Combinatorics REGS program began in 2004. 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 faculty, visitors, and students, the problems come from conferences, web pages, journal articles, etc. The program provides an early exposure to research and exposition, thereby increasing mathematical maturity and easing the transition from coursework to research. We meet MWF 10:30-12 and 2-5 (more intensively during the first week). Many joint papers have emerged. Projects may or may not lead to thesis research. Further information about the status and development of the program appears in the yearly reports: 2012; 2011; 2010; 2009; 2007; 2006; 2005; 2004.

Note on MathJax: Pages since the middle of Summer 2011 use MathJax. Notation is typed in equation mode of TeX, between dollar signs or double dollar signs. Page-loading incurs a slight delay while Mathjax computes the display of notation. The appearance can be refined by right-clicking on notation and exploring the menus; changes to settings should persist.

Preparing web pages for posting: Mathjax does not recognize TeX font commands for text or layout; html is still needed to italicize words, make tables, etc. html swallows input after "<"; use "\lt" for "less than" and "\gt" for "greater than" in notation. html character codes start with "&" and end with ";" (do not omit ";"). Applying an html converter to a tex document or using an html editor does NOT produce useful files; type plain text into the supplied template and use TeX only for the notation. Clean up garbled characters copied from MathSciNet for references. Test the appearance of your page in a browser before submission; it should use the same style as the pages already posted.

Problems presented in Summer 2013

For basic terminology not given on problem pages, see the Glossary.
  1. Gray codes on proper k-colorings
  2. List coloring of kth powers
  3. Rainbow connection number
  4. Dominating (covering) closed trails
  5. Independent domination in regular graphs
  6. Factors in regular graphs
  7. Defining sets in graph colorings
  8. Chromatic villiany
  9. Monochromatic coverings of edge-colored graphs
  1. Induced saturation numbers
  2. Almost k-choosable graphs
  3. Color-critical planar graphs (missing)
  4. Removal of obstacles to connection (missing)
  5. Monochromatic disjoint-tree coverings
  6. Ramsey-minimal saturation number (missing)
  7. 3-dimensional stable marriage

Problems presented in Summer 2012

The 2012 RESULTS PAGE lists results obtained in REGS toward or related to the problems proposed.
  1. Hamiltonian cycles in prisms
  2. Ore-type condition for equitable coloring
  3. Vizing's Conjecture on domination
  4. Linear discrepancy of posets
  5. Hypergraphic sequences
  6. Paintability and sum-paintability
  7. Rainbow spanning trees
  8. Saturation number for Ramsey-minimal families
  9. Graph generation
  10. Choosability of planar graphs
  11. Nonexistence of $k$-Friendship graphs
  12. On-line vertex ranking
  13. Forbidden subgraph pairs for pancyclicity
  14. Obstacle number of graphs
  15. On-line sum paintability
  16. Bar visibility graphs and digraphs
  17. Visibility and $k$-link visibility graphs
  18. Non-convex crossing sequences
  19. Potential-Ramsey numbers
  20. Disjoint 1-factors
  21. Crossing numbers in linear drawings
  22. Game saturation number
  23. Graph sandwich problems
  24. Universal cycles for permutations
  1. Erdős-Faber-Lovász Conjecture
  2. DeBruijn cycles with distance constraints
  3. $k$-trees and $k$-prism Hamiltonicity
  4. Homomorphically irreducible spanning trees
  5. Toughness and cyclability
  6. Honest-men and liars
  7. Stationary sets of vectors
  8. Harmonious coloring
  9. Increasing paths in edge-ordered graphs
  10. Improper choosability
  11. Game incidence chromatic number
  12. Large isomorphic edge-disjoint subgraphs
  13. Dynamic coloring, revisited
  14. Disjoint chorded cycles
  15. Forcing sets for quasirandomness
  16. Modular neighbor-distinguishing edge-coloring (SOLVED)
  17. Hypergraphs with $p$ perfect matchings
  18. Saturation spectrum
  19. Thickness for improper colorings
  20. Manicham-Miklós-Singhi Conjecture
  21. Higher-genus pagenumber (stub)
  22. Frankl-Füredi Conjecture
  23. On-line size Ramsey number
  24. Covering and packing with homothetes
  25. Good Edge-labeling of graphs

Problems presented in Summer 2011

The 2011 RESULTS PAGE lists results obtained in REGS toward or related to the problems proposed.
  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