This is joint work with Maria Axenovich and André Kézdy.

A graph G embeds in the k-dimensional hypercube if and only if p(G) < k and every cycle in G is a parity walk. Consequently, p(G) > ceiling(lg n(G)), and equality holds for paths and even cycles. When n is odd, p(C_n)=p'(C_n)=1+ceiling(lg n). Also, p(K_2,n)=p'(K_2,n), with value n when n is even and n+1 when n is odd. The main result is that p'(K_n)=2^ceiling(lg n)-1 for all n. Furthermore, the optimal coloring for K_n is unique when n is a power of 2 and completely described for all n. Also p(K_n)=p'(K_n) when n < 16.

A graph G is \gamma-edge-critical if \gamma(G+e)<\gamma(G) for each edge e\notin E(G). It is \gamma-vertex-critical if \gamma (G-v)<\gamma(G) for every vertex v\in V(G). The structure of \gamma-edge-critical graphs and \gamma-vertex-critical graphs is not well understood, even when \gamma(G)=3. We present new results on both classes that involve matchings.

In 1996, Matheson and Tarjan proved that a triangulated disc with n vertices has domination number at most n/3, and thus so does every n-vertex triangulation. We will present recent work toward extending this result to graphs of higher genus.

Reed conjectured in 1996 that if G is a cubic graph with n vertices, then \gamma (G) < \lceil|V(G)|/3\rceil. This conjecture was very recently shown to be false by Kostochka and Stodolsky. We will close by discussing new results pertaining to this conjecture.

First, the concept of a generalized Stirling number pair can be characterized by a pair of inverse relations, in which the problem of expansion of A(t)f(g(t)) (a composition of any given formal power series) can be constructively solved with the aid of Sheffer-type differential operators. Using the generalized Stirling number pair, we establish an inversion formula that can be applied to find an expansion of an analytic function f in terms of a sequence of Sheffer-type polynomials. The result can be readily extended to the higher-dimensional setting.

Secondly, multivariate rational exponential Lagrange interpolation formulas, Hermite interpolation formulas, and Hermite-Fejér interpolation formulas of the Newton type are established using Carlita's inversion formulas. By letting q -> 1, the obtained formulas reduce to the corresponding multivariate polynomial interpolation formulas with combinatorial form.

Finally, we provide a wide class of Möbius inversion formulas in terms of the generalized Möbius functions and its application to the setting of the Selberg multiplicative functions.

A classical theorem of Vizing states that the edges of every graph G with maximum degree D can be colored by at most D+1 colors so that no two incident edges have the same color; that is, the chromatic index of G is at most D+1. We show that for every e>0 there exists g such that the circular chromatic index of a graph G with maximum degree D whose girth is at least g does not exceed D+e. Note that the index must be at least D because the line graph of such a graph contains a clique of order D.

Our research is motivated by a conjecture of Jaeger and Swart 1979 (which turned out to be false) that high girth cubic graphs have chromatic index 3. Our results imply that the relaxation of the conjecture to circular colorings is true: the circular chromatic index of high girth cubic graphs is close to 3. Among the ingredients of our proof are recent results on systems of independent representatives and hypergraph matchability by Aharoni, Haxell, Meshulam, and others, which we also briefly survey during the talk.

This work is joint with Tomas Kaiser, Riste Skrekovski, and Xuding Zhu.

In this talk, we prove sharp upper bounds on \gamma_R(G) when G is a connected n-vertex graph with minimum degree k, where k {1,2}. We also find sharp Nordhaus-Gaddum type bounds. This is joint work with Erin Chambers, Bill Kinnersley, and Douglas West.

In this talk, we investigate an Ore-type analogue of the Sauer-Spencer Theorem. Let \theta(G)=\max{d(u)+d(v): uv\in E(G)}. We show that if \theta(G₁)\Delta(G₂) < n, then G₁ and G₂ pack. We also characterize the pairs (G₁,G₂) of n-vertex graphs that do not pack but satisfy \theta(G₁)\Delta(G₂)=n. Some open problems will be mentioned as well.

This is joint work with Alexandr Kostochka.

In this talk we present asymptotic bounds for the linear discrepancy of the product of three k-chains and the linear discrepancy of the product of four k-chains. In three dimensions, the value is (3/4+o(1))k³. In four dimensions, the value is (7/8+o(1))k⁴. The upper bound construction generalizes easily to d dimensions.

This is joint work with Douglas B. West.

Graphs with chi'(G)=W(G) are called elementary. Goldberg and Seymour independently conjectured in the 1970s that all graphs G with chi'(G) >= D(G)+2 are elementary. For an integer m, let J_m denote the class of all graphs G such that chi'(G) > (mD(G)+m-3)/(m-1). Shannon's Theorem implies that J₃ is empty. Always J_m\subseteq J_m+1, and the union of all J_m with m >= 3 consists of all graphs G such that chi'(G) >= D(G)+2.

The conjecture has previously been proved for all graphs in J_m for odd m up to 11. We use an extension of the method Tashkinov used for m=11 to prove that every graph in J₁₃ is elementary. The proof yields a polynomial-time algorithm to properly color the edges of every graph G with at most floor[(13chi'(G)+10)/12] colors.

Andrews, Paule, and Riese found a generalization of these families that they enumerated with the help of MacMahon's partition analysis. In this work, we formulate a further generalization and show how to reduce the enumeration problem to computing permutation statistics. In cases where those statistics can be computed, nice enumeration formulas emerge.

This is joint work with Sunyoung Lee.

(r=0): 1 1
(r=1): 1 2 1
(r=2): 1 3 2 3 1
(r=3): 1 4 3 5 2 5 3 4 1

Stern himself proved in 1858 that every ordered pair (a,b) of relatively prime positive integers occurs exactly once as the pair (s(n),s(n+1)), and the binary representation of n is encoded by the continued fraction representation of a/b. The maximum values in the rth row is the (r+2)-nd Fibonacci number. The entries in the rth row sum to 3^r + 1; the sum of the cubes of the entries is 9*7^r-1 (for r > 0). The Stern sequence also has many interesting divisibility properties: s(n) is even iff n is a multiple of 3; the set of n for which s(n) is a multiple of 3 has a simple recursive description. The set of n for which s(n) is a multiple of the prime p has density 1/(p+1). Further, s(n) is the number of binary representations of n-1, if one allows digits from {0,1,2}. If n is odd and m is the integer whose base 2 representation is the reversal of n's, then s(n) = s(m) and s(n+1)s(m+1) = 1 mod (s(n)). The Stern sequence affords a clear understanding of the alluringly-named Minkowski ?-function, which gives a strictly increasing map from [0,1] to itself, taking the rationals to the dyadic rationals, and the quadratic irrationals to the non-dyadic rationals. There are few other mathematical objects which are as generous in their grooviness; as one final example, s(729) = 64.

This talk will be rather elementary and accessible to alert undergraduates.