MSCS Seminar Calendar

Monday December 5, 2016
pdf * 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.

pdf * 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
pdf * 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
pdf * 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
pdf * Commutative Algebra Seminar
TBA
Claudia Miller (Syracuse)
4:00 PM in SEO 427
TBA
Monday January 23, 2017
pdf * Commutative Algebra Seminar
TBA
Axel Stabler (University of Michigan)
1:00 PM in SEO 427
TBA

pdf * Geometry, Topology and Dynamics Seminar
TBA
Gabriele La Nave (UIUC)
3:00 PM in SEO 636
TBA

pdf * Algebraic Geometry Seminar
TBA
Chenyang Xu (MIT / BICMR)
4:00 PM in SEO 427
TBA
Monday January 30, 2017
pdf * 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
pdf * Geometry, Topology and Dynamics Seminar
TBA
Caglar Uyanik (UIUC)
3:00 PM in SEO 636
Friday February 10, 2017
pdf * Departmental Colloquium
TBA
Carlos Kenig (The University of Chicago)
3:00 PM in SEO 636
TBA
Monday February 13, 2017
pdf * 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
pdf * Geometry, Topology and Dynamics Seminar
TBA
Carolyn Abbott (University of Wisconsin, Madison)
3:00 PM in SEO 636
Monday March 6, 2017
pdf * Combinatorics Seminar
TBA
Tom Bohman (Carnegie Mellon University)
2:00 PM in SEO 612

pdf * Geometry, Topology and Dynamics Seminar
TBA
Malik Obeidin (UIUC)
3:00 PM in SEO 636

pdf * Analysis and Applied Mathematics Seminar
TBA
Jun Kitagawa (Michigan State University)
4:00 PM in SEO 636
TBA
Monday March 13, 2017
pdf * Combinatorics Seminar
TBA
Yi Zhao (Georgia State)
2:00 PM in SEO 612

pdf * Geometry, Topology and Dynamics Seminar
TBA
Caleb Ashley (University of Michigan)
3:00 PM in SEO 636
TBA
Wednesday April 12, 2017
pdf * Algebraic Geometry Seminar
TBA
Samuel Grushevsky (Stonybrook)
4:00 PM in SEO 427
TBA
Wednesday April 19, 2017
pdf * Statistics Seminar
TBA
Xi Geng (Carnegie Mellon University)
4:00 PM in SEO 636
Friday April 21, 2017
pdf * Departmental Colloquium
TBA
Sándor Kovács (University of Washington)
3:00 PM in SEO 636
TBA
Wednesday April 26, 2017
pdf * Algebraic Geometry Seminar
TBA
Tommaso de Fernex (University of Utah)
4:00 PM in SEO 427
TBA
Friday April 28, 2017
pdf * Departmental Colloquium
Height Zeta Functions
Yuri Tschinkel (NYU and Simons Foundation )
3:00 PM in TBA
Atkin Memorial Lecture
HTML 5 CSS FAE
UIC LAS MSCS > seminars > seminar calendar