One of the problems on Hilbert's 1900 list asked whether every positive rational function can be written as a sum of squares of rational functions. Its affirmative resolution by Artin in 1927 was a breakthrough for real algebraic geometry. The talk addresses the analog of this problem for positive semidefinite noncommutative rational functions. More generally, a rational Positivstellensatz on matricial sets given by linear matrix inequalities will be presented; a crucial intermediate step is an extension theorem on invertible evaluations of linear matrix pencils, which has less to do with positivity and ostensibly more to do with representation theory. One of the consequences of the Positivstellensatz is an algorithm for eigenvalue optimization of noncommutative rational functions. Finally, some contrast between the polynomial and the rational Positivstellensatz in the noncommutative setting will be discussed.

The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/log n for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). Based on joint work with Kalen Patton and Lutz Warnke.

A classical result of Erdős and Pósa states that a graph without many disjoint cycles contains a small vertex set intersecting every cycle. The analogous statement fails however for odd cycles, as can be shown by large projective planar grids. In 1987, Dejter and Neumann-Lara raised the question of when this approximate packing-covering duality holds for cycles of length L mod M, and there had been minimal progress on this problem until recently. There are similar questions on packing A-paths (paths meeting a vertex set A at exactly its endpoints) with modularity constraints. Casting these problems in the more general setting of group-labelled graphs and studying their structure, we obtain a complete characterization of the integer pairs L and M for which the above approximate duality holds for A-paths and cycles of length L mod M. Joint work with Robin Thomas and with Pascal Gollin, Kevin Hendrey, O-joung Kwon, and Sang-il Oum.

We study asymptotic homological properties of random quadratic monomial ideals in a polynomial ring R = k[x_1, . . . , x_n], utilizing methods from the Erd\"os-R\'enyi model of random graphs. Here we consider a graph on n vertices and exclude an edge (corresponding to a quadratic generator of the ideal I) with probability p, and consider algebraic properties as n tends to infinity. Our main results involve fixing the edge parameter p = p(n) so that asymptotically almost surely the Krull dimension of R/I is fixed. Under these conditions we establish various properties regarding the Betti table of R/I, including sharp bounds on regularity and projective dimension and distribution of nonzero Betti numbers. These results extend work of Erman-Yang, who studied such ideals in the context of conjectured phenomena in the nonvanishing of asymptotic syzygies. Our results use collapsibility properties of random clique complexes and Garland's method regarding spectral gaps of graphs, and in particular rely on the underlying field in some cases. This is joint work with Andrew Newman.

We give a new combinatorial criterion for quotients of affine semigroup rings by monomial ideals to be Cohen-Macaulay, by computing the homology of finitely many polyhedral complexes. This provides a common generalization of well-known criteria for affine semigroup rings and monomial ideals in polynomial rings. This is joint work with Laura Matusevich.