Results: Combinatorics REGS 2010

1. Mixed Ramsey theory
2. Consequences of the Berge-Fulkerson Conjecture
3. Largest graphs having p perfect matchings
   (Hartke, Stolee, West, Yancey) For any fixed p, there is an n-vertex graph with more than n²/4 edges that has exactly p perfect matchings. In particular, letting f(n,p) be the maximum number of edges in an n-vertex graph having exactly p perfect matchings, they proved that f(n,p)&ge n²/4+c_p for sufficiently large n, with c_p being at least the number of 1s in the binary representation of p-1. Although it is not known whether c_p is monotonic in p, the values of c_p can be as large as O(ln p / ln ln p)².
4. Realizing degree lists with few perfect matchings(O, West) To gain some insight on the problem, it may be helpful to know the maximum number of edges in a graph with minimum degree d that has no perfect matching. More generally, we have determined the n-vertex graphs of minimum degree d that have the most edges among those not having a matching of size (n-a)/2, where a has the same parity as n.
5. Total bar visibility number
6. On-line Chain-Partitioning for Semiorders
(Biró, Kinnersley, Milans, Hannasch, Zamani) Let f(w) be the minimum number of colors that suffice for Algorithm to color points in on-line fashion when Spoiler is restricted to w points in any half-open interval. For α∈(0,1], let f_α(w) denote the sufficient number of colors when Spoiler is further restricted to place points only at multiples of α. As α decreases toward 0, f_α(w) increases. For all w, there exists α such that f_α(w)=f(w). For particular α, it has been shown that f_1/2(w)=w and 5w/4 ≤ f_1/3(w) ≤ 3(w+1)/2.
7. Tournaments and generalized score sequences The question of characterizing FIFA score lists when the numbers of wins, losses, and ties for each team are known reduces to characterizing degree lists for oriented graphs. Given any realization of the wins and losses, the missing edges will always yield a realization of the ties, since for each team #ties = (n-1) - (#wins + #losses) = (n-1) - (out-degree + in-degree). Thus it suffices to check that the (win,loss) list is realizable by an oriented graph (and that in fact for each team #wins + #losses + #ties = n-1).
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
(Biro, Hartke, Isaak, McDonald, Stolee, West) Reconstruction of trees from ideal sizes is equivalent to reconstruction of forests. For trees, the rank-sizes are reconstructible, as are the bottom three levels of the tree. It is well-known that the pairs (|upset|,|downset|), given for just the individual elements, determine the poset within the family of interval orders.
15. 3-cordial colorings
    (Many authors) The following classes of graphs are 3-cordial: forests, connected unicyclic graphs, and any cartesian product of any number of paths. The latter uses a theorem that if G and H are 3-cordial, and the number of vertices or the number of edges of G or H is divisible by 3, then the cartesian product of G and H is 3-cordial. It is almost certainly also true that graphs in which each component is unicyclic are 3-cordial, but this has not been completed.
       Pechenik and Wise studied Z₂²-cordial colorings. They showed that all paths except P₄ and P₅ have such colorings, and all cycles with lengths other than 4, 5, and odd multiples of 2 have such colorings. Also, hypercubes with dimension at least 3 are Z₂²-cordial.
       Pechenik studied A-cordial colorings for various groups A. For fixed A, he showed that there are infinitely many A-cordial cycles and infinitely many A-cordial paths. If A has order n, then the complete k-partite graph having kn^2 vertices and partite sets of size n² is A-cordial for k>2. When A is not abelian, corresponding results hold for appropriate orientations of the graphs.
16. Yao's table storage problem
    (Howard, Kezdy, Milans, West - maybe others) With two probes, adaptively, key spaces of size at least 3n-4 can be handled. In the weaker model that makes only two simultaneous probes, at most about 2n²lgn keys can be handled. When n=3, the maximum that can be handled in this model is between 15 and 18 (Howard).
17. Star-critical Ramsey numbers
18. Ehrenfeucht-Fraissé game & subgraph isomorphs
19. Edge-antipodal colorings of hypercubes
Kolb, Pechenik, and Wise gave explicit proofs that every edge-antipodal coloring of a hypercube with at most 5 dimensions has a monochromatic path joining antipodes. This was previously known only by computer search.
20. Segment orders
21. Immersion order on graphs (Butterfield, Hartke, LeSaunier, Milans, Stolee, Wenger) This group has studied immersion-closed families. Outerplanar graphs are those not containing subdivisions of K₄ or K_2,3; they have characterized the graphs not containing immersions of K₄ or K_2,3. Also, the graphs not containing an immersion of the kite (K₄-e) are the cacti, and the graphs with maximum local edge-connectivity bounded by k are those not containing an immersion of the graph consisting of k-1 triangles sharing a common edges. Extremal problems are also being studied. It is conjectured that (t-2)[n-(t-1)/2] is the maximum number of edges in an n-vertex graph not containing an immersion of K_t; this is true up to t=5.
22. Sorting by k-ary comparisons (McLaughlin, McDonald?) There has been some success generalizing results of Aigner for the binary comparison model
23. Circumference of claw-free graphs (stub)
24. Revolutionaries and spies (Butterfield, Cranston, Puleo, West, Zamani) In large complete bipartite graphs, ⌈7r/10⌉ spies can protect against meetings of size 2 among r revolutionaries, and this is sharp. There may be some extensions to For meetings of size m, cr/m spies are enough to win, where c = 1/(2-√2). As an upper bound when m is large, the number of spies needed is at least 3r/(2m). Hypercubes and generalizations of cycles are also worth studying.
25. Monotone Hamiltonian paths in hypercubes
26. Undirected edge geography (stub)
27. Dynamic coloring (O, Jahanbekan, Kim, Kim, ???) An r-dynamic k-coloring is a proper coloring that uses at least min{r,d(v)} colors on the neighborhood of each vertex v; the minimum k permitting such a coloring is the r-dynamic chromatic number χ_r(G)). Note that χ₃ is 10 for the Petersen graph. The group has studied products. If δ(G)≥r, then χ_r(G \box H) ≤ max{χ_r(G),χ(H)}. The r-dynamic chromatic number has been computed for the cartesian product of two paths. If G is d-regular, then χ_r(G) ≤ rχ(G) for large enough d.
       The dynamic chromatic number (which is just χ₂(G)) was studied in REGS for planar graphs and for graphs with bounded maximum average degree (Mad). What girth is needed to guarantee χ₂(G)≤4 when G is planar? Girth at least 7 implies that the dynamic choice number of a planar graph is at most 4; the proof uses discharging and is short. Sharpness is shown by the graph obtained from a planar graph with choice number 5 by subdividing each edge. Also, there are planar graphs with dynamic chromatic number 4 and arbitrarily large girth.
       Furthermore, the dynamic choosability is at most 4 when Mad(G)<8/3. Sharpness is shown by subdividing each edge of K₅. More generally, if Mad(G)<4k/(k+2), then the dynamic choosability of G is at most k.
28. Erdős-Ko-Rado problem for graphs
29. Linear and weak discrepancy in posets
Kevin Milans constructed posets with linear discrepancy (2-o(1))r, where r is the maximum number of elements incomparable to a single element, thereby disproving the conjecture of Tanenbaum, Trenk, and Fishburn.
30. Disjoint maximal independent sets (stub)
31. Edge-reconstruction of multigraphs Dan McDonald et al. have proved the edge-reconstructibility of non-simple multigraphs whose underlying simple graphs fall in any of the following categories: Disconnected with at least two nontrivial components, Edge-transitive, Regular, Trees. They also proved the edge-reconstructibility of other multigraphs with certain restrictions on where multiedges occur.
32. Matching in geometric graphs
33. Expandable L(2,1)-labelings
34. Crossings in horizontal drawings Yancey has improved the lower bound on the supremum of the ratio of opt(G) to LB(G). Previously it was 13/11; his improved lower bound is 12/10. The known upper bound is 1.2964.
35. Group connectivity of graphs
36. Nowhere-zero solutions to linear equations
37. Chaos: toppling piles of tokens For the normal version (win by capturing all vertices), it was already known that Player 1 wins on K_n for all n and wins C_n if and only if n is odd. In REGS, McLaughlin and Reiniger showed that Player 1 wins on a tree if and only if the number of vertices is even. Also, each player has a strategy that avoids losing until |V(G)|-1 turns have been played. They conjecture that Player 2 wins on K_a,b if and only if a and b are both even, which they have proved for the cases where min{a,b}>2 and ab is even. They ask whether the winner on the graph obtained by identifying one vertex of G with one vertex of H is always the same as the winner on the disjoint union G+H. Digraph analogues have been proposed. The misere version (win by forcing the opponent to capture all vertices) has also been studied. Others working on these problems include Hannasch, Kinnersley, and Puleo.
38. Difference graphs
39. Implications between linkage properties Hehui Wu answered both questions in the negative, by constructing an example that gives a "no" answer to the more restricted question.
40. Trail-ordered and circuit-ordered graphs (stub)
41. Spatial embeddings of graphs
42. Grab the Gold! - A tree-eating game
(Arroyo, Liu, Mahoney, Olsen, Work, West) Partial results toward Player 1 getting at least half the weight on trees with even order. This is true on double-stars and on trees obtained from double-stars by subdividing all but the central edge. Tyler Seacrest may have proved the conjecture.
43. Maker-Breaker games on grids In the game where Maker seeks the corners of a square (of any size), Maker wins in five turns on every n-by-n grid with n≥13. This is sharp in terms of the number of turns required. In general, if Maker seeks the points of any "pattern" in any number of dimensions, Gallai's Theorem and a simple strategy-stealing argument imply that he succeeds when the board is sufficiently large. It might be worthwhile to consider the biased game, since then the strategy-stealing argument fails. (Probably Maker still wins against any constant bias.)
       In the game where Maker seeks as large a transversal as possible on an n-by-n board, Maker can obtain a transversal of size n in n+1 turns when n≥5 (the results are known and slightly different for n≤4). The result is best possible in terms of both transversal size and number of turns needed. Maker can also obtain a transversal of size n-1 in n-1 turns, but this would hinder his ability to quickly obtain a transversal of size n.
44. Havel-Hakimi residue and independent sets
45. Quack number
Reiniger, LeSaulnier, Wenger, and West are studying the quack numbers of complete graphs and complete bipartite graphs.
46. F-saturated graphs
47. Chromatic number vs. cliques
A computer search by Kolb showed that Q(9,5)=4.
48. Sorting by 3-branches
49. Turán problems for co-degree
50. Coloring paths in trees
51. Acyclic orientation game
52. Monophilic graphs (stub)
53. Coloring the square of the Kneser graph (stub)