Events

Title: Wires, bits, and the cost of sorting

Abstract: How hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?

Title:  A threshold for fractional Sudoku completion

Abstract: The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells.  The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once.  We can extend Sudoku so that the boxes are $h$-by-$w$, and the overall array is $n$-by-$n$, where $n=hw$.  The puzzle is now similar to completing a latin square of order n, except of course that Sudoku has an additional box condition.

Title: The Container method for Enumerating Triangle-free graphs

Abstract: The container method is a tool for bounding the number of independent sets in graphs and can be generalized to hypergraphs. It utilizes the observation that independent sets are found in clusters or “containers” within the graph. One application of this method is to bound the number of finite objects with some forbidden substructure. For example, we can bound the number of graphs on N vertices that do not contain K₃ as a subgraph, that is, the number of Triangle-free graphs on N vertices. We will take a look at finding this bound using the container method.

Title: Prophets, philosophers, and online algorithms

Abstract: In online Bayesian selection problems, a seller is faced with a stream of buyers arriving sequentially. Each arriving buyer makes, for each item on sale, a take-it-or-leave-it offer drawn from some known distribution, which the seller must immediately either accept or decline. It is common to compare the seller's benefit to the optimal offline solution, obtained by a "prophet'' who knows the future. However, the seller might not even be able to compete with the optimal online algorithm, which may be computationally intractable to run. In this case the optimal online algorithm is obtained by a "philosopher'' with sufficient time to think (compute).  In this talk I will discuss some developments on online algorithms efficiently approximating this philosopher.

Title: Nash-Williams Orientation for Infinite Graphs

Abstract: Nash-Williams proved in 1960 that an edge-connectivity of 2k is sufficient for a finite graph to admit a k-arc-connected orientation and conjectured that the same holds for infinite graphs. We show that the conjecture is true for locally finite graphs with countably many ends.

This is joint work with Max Pitz and Marcel Koloschin.

Title: Online edge colouring

Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ can be edge-colored using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime.

Title: Eigenvalues of high dimensional Laplacian operators

Abstract: A simplicial complex is a topological space built by gluing together simple building blocks (such as vertices, edges, triangles and their higher dimensional counterparts). Alternatively, we can define a simplicial complex combinatorially, as a family of finite sets that is closed under inclusion. In 1944, Eckmann introduced a class of high dimensional Laplacian operators acting on a simplicial complex. These operators generalize the Laplacian matrix of a graph (which can be seen as a 0-dimensional Laplacian), and are strongly related to the topology of the complex (and in particular, to its homology groups).

Title: The non-backtracking matrix

Abstract: A non-backtracking walk in a graph is any traversal of the vertices of a graph such that no edge is immediately repeated. The non-backtracking matrix of a graph is indexed by the directed edges of the graph, and encodes if two edges can be traversed in succession. Since this matrix is not symmetric, the question of when the matrix is diagonalizable is of interest to those who study it. Equivalently, such graphs have a non-trivial Jordan block. In this talk, I will present an overview of the non-backtracking matrix, including its history and applications. Finally, I will present recent results about graphs with non-trivial Jordan blocks for the non-backtracking matrix from joint work with Kristin Heysse, Kate Lorenzen, and Xinyu Wu.

Title: Pretty Good Fractional Revival via Magnetic Fields - theory and examples

Abstract: I will discuss the notion of PGFR relative to a given subset of nodes of a graph. This is a generalization of the more standard (pretty good) fractional revival between 2 nodes. In the process, I will introduce the proper generalization of cospectrality to the fractional setting, and give the appropriate extensions of methods already in use for the 2-vertex case. These include the Kronecker condition and the field-trace method. I will conclude by giving various families of examples of PGFR in the presence of (transcendental) magnetic fields.

Title: A new shifted Littlewood-Richardson rule

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract: As Littlewood-Richardson rules compute linear representation theory of symmetric groups and cohomology of ordinary Grassmannians, shifted Littlewood-Richardson rules compute analogous projective representation theory of symmetric groups and cohomology of orthogonal Grassmannians. The first shifted Littlewood-Richardson rule is due to Stembridge (1989), building on a natural generalization by Sagan and Worley (1979/1984) of the jeu de taquin algorithm to shifted Young tableaux. We give a new shifted Littlewood-Richardson rule that requires consideration of fewer tableaux than Stembridge's rule and appears to involve an easier check on each. Our rule derives from applying old ideas of Lascoux and Schützenberger (1981) to the study of Haiman's mixed insertion (1989) and Serrano's shifted plactic monoid (2010). (Joint work with Oliver Pechenik).