# MSCS Seminar Calendar

Monday December 5, 2016

**Combinatorics Seminar**

Hanani--Tutte theorem for c-planarity with pipes

Radoslav Fulek (Institute of Science and Technology Austria)

2:00 PM in SEO 612

We resolve in the affirmative a conjecture of M.~Skopenkov (2003) generalizing the classical Hanani--Tutte theorem to the setting of approximating maps of graphs in the plane by embeddings. Our proof of this result is constructive and almost immediately implies that flat c-planarity can be tested in polynomial time if
a plane drawing of the cluster adjacency graph is given as a part of the input.
More precisely, an instance of this problem consists of (i) a planar graph $G$ whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region $R$ of the plane given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise non-intersecting ``pipes''
corresponding to the bundles, connecting certain pairs of these discs.
We are to decide whether $G$ can be embedded inside $R$ so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.
Joint work with Jan Kyncl.

**Ph.D. Thesis Defense**

Graphical Algorithms for Finding the Nucleolus of Binary-Valued Matching Games

John Hardwick (University of Illinois at Chicago)

3:00 PM in SEO 612

In cooperative game theory, the class of assignment games models a hypothetical market with two groups of people (for instance, buyers and sellers, or men and women). When a player from one group pairs up with a player from the other group, they receive a payoff, which is specified for each potential pair. The players work together to maximize the total payoff for the market. But then the real problem arises, which is how to split that payoff amongst everyone.
One popular solution for cooperative games, and especially for assignment games, is the nucleolus. This is a way of splitting the payoff which maximizes everyone's satisfaction, and minimizes possible incentive for deviating from the group. In this thesis, we expand upon previous work by Solymosi and Raghavan, which gives an algorithm for calculating the nucleolus of assignment games. We focus on a special case, in which all pairs' payoffs are either 0 or 1. This can be interpreted as a measure of compatibility for the pair, and the way each pair splits their payoff can be viewed as their balance of power. In this special case, the previous algorithm can be recontextualized and streamlined using purely graphical methods.
We also provide an algorithm for a more general class of games, called matching games. These are defined similarly to assignment games, but without the restriction that the market must be bipartite. This gives us deeper insight into societal applications: for instance, the matching game can be used to model a marriage market in our modern society, while the assignment game would only apply to societies where same-sex marriage is not allowed.

Thursday December 15, 2016

**Logic Seminar**

Accessible categories and abstract elementary classes

Mike Lieberman (Masaryk University. Brno)

4:00 PM in SEO 427

Bootstrapping structural properties, via accessible images
We discuss recent joint work with J. Rosicky, [LR], involving new applications of an as-yet-underappreciated tool for the analysis of categories of structures arising in abstract model theory, namely that, under the assumption of sufficiently strongly compact cardinals, the (powerful) image of any accessible functor is accessible ([MP], refined in [BrR]). Although some of these applications are technical (tameness of abstract elementary classes, i.e. AECs, in [LR16]; strong metric tameness of metric AECs in [LR]), we focus on two very simple ones: the amalgamation and joint embedding properties. The basic insight is that each property amounts to a question of the following form: given a diagram of shape A in category of structures K, can it be completed to a diagram in K of shape A'?
We can then rephrase this problem in terms of the forgetful functor U:K^{A'}--->K^A, whose (powerful) image consists precisely of the completable diagrams. As U is accessible, the theorem of [BrR] implies that this image is k-accessible for sufficiently strongly compact k, from which it follows that completability of diagrams involving objects of size up to k implies the completability of diagrams of objects of arbitrary size. That is, this is precisely what one needs to bound the Hanf numbers for amalgamation and joint embedding. This generalizes the results of [BaBo] from AECs to general accessible categories, thereby encompassing e.g. metric AECs, mu-AECs, and so on, with the added benefit of being almost purely visual, replacing delicate syntactic manipulations with simple questions about diagrams in well-behaved categories.
[BaBo] Baldwin, John, and Will Boney. Hanf numbers and presentation theorems in AECs. To appear in Beyond First Order Model Theory, CRC Press.
[BrR] Brooke-Taylor, Andrew, and Jiri Rosicky. Accessible images revisited. Submitted, arXiv:1506.01986.
[LR] Lieberman, Michael and Jiri Rosicky. Bootstrapping structural properties, via accessible images. Submitted, arXiv: 1610.07816.
[LR16] -------------------. Classification theory for accessible categories. Journal of Symbolic Logic, 81(1): 3048-3066 (2016).
[MP] Makkai, Michael and Robert Par\' e. Accessible Categories: The Foundations of Categorical Model Theory. AMS 1989.

Mike works at the intersection of category theory and model theory. He will be around all
of next week.

Monday January 9, 2017

**Geometry, Topology and Dynamics Seminar**

Polyhedra inscribed in quadrics and their geometry.

Sara Maloni (University of Virginia)

3:00 PM in SEO 636

In 1832 Steiner asked for a characterization of polyhedra which can be inscribed in quadrics. In 1992 Rivin answered in the case of the sphere, using hyperbolic geometry. In this talk, I will describe the complete answer to Steiner's question, which involves the study of interesting analogues of hyperbolic geometry including anti de Sitter geometry. Time permitting, we will also discuss future directions in the study of convex hyperbolic and anti de Sitter manifolds.
(This is joint work with J. Danciger and J.-M. Schlenker.)

Thursday January 12, 2017

Monday January 23, 2017

Monday January 30, 2017

**Geometry, Topology and Dynamics Seminar**

Kirwan surjectivity for quiver varieties

Tom Nevins (UIUC)

3:00 PM in SEO 636

Many interesting hyperkahler, or more generally holomorphic symplectic, manifolds are constructed via hyperkahler/holomorphic symplectic reduction. For such a manifold there is a “hyperkahler Kirwan map,” from the equivariant cohomology of the original manifold to the reduced space. It is a long-standing question when this map is surjective (in the Kahler rather than hyperkahler case, this has been known for decades thanks to work of Atiyah-Bott and Kirwan). I’ll describe a resolution of the question (joint work with K. McGerty) for Nakajima quiver varieties: their cohomology is generated by Chern classes of “tautological bundles.” If there is time, I will explain that this is a particular instance of a general story in noncommutative geometry. The talk will not assume prior familiarity with any of the notions above.

Monday February 6, 2017

Friday February 10, 2017

Monday February 13, 2017

**Combinatorics Seminar**

On the Ramsey-Turan number with small independence number

Andrzej Dudek (Western Michigan)

2:00 PM in SEO 612

In this talk we consider the following question motivated by the classical Turan and Ramsey theorems. What is the maximum number of edges in a K_t-free graph G of order n with the s-independence number smaller than f(n) (where the s-independence number is the maximum number of vertices in a K_s-free induced subgraph of G)? This problem attracted a considerable amount of attention and has been mainly studied for f not too much smaller than n. In this talk we consider f(n) = n^d for d<1. In particular, we show that the maximum number of edges in a K_{s+1}-free graph of order n with the s-independence number at most n^d (for any 1/2 < d < 1) is roughly speaking n^{1+d}.

Monday February 27, 2017

Monday March 6, 2017

Wednesday April 12, 2017

Wednesday April 19, 2017

Friday April 21, 2017

Wednesday April 26, 2017