Events

Title: Two counterexamples related to chi-boundedness

Abstract:

This will be a joint talk with two parts.

Sophie Spirkl: I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r. 

Title: Rotational Differential-Linear Cryptanalysis of ARX Ciphers

Abstract:

The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. We further extend this framework by replacing the differential part of the attack by rotational differentials.

Title:  A curious identity between the orthogonal Brezin--Gross--Witten integral and Schur symmetric functions via b-deformed monotone Hurwitz numbers

Abstract:

This talk is intended for an algebraic combinatorial community and no prior knowledge is required. All the difficult words (Hurwitz numbers, KP hierarchy, HCIZ and BGW integrals, Jack symmetric functions, the b-conjecture) will be explained and gently introduced.

Title: On reverse mixing in quantum walks

Abstract:

A random walk on a connected undirected graph mixes to the principal eigenvector. We consider a continuous-time quantum walk to reverse this process: starting with the principal eigenvector, can we reach an arbitrary vertex if we were to place a loop on the target vertex?

Title: Homomorphism counts in robustly sparse graphs

Abstract:

For a fixed graph H and for arbitrarily large host graphs G, the number of homomorphisms from H to G and the number of subgraphs isomorphic to H contained in G have been extensively studied when the host graphs are allowed to be dense.

Title: Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

Abstract:

The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis.

Title: Packing and covering balls in planar graphs

Abstract:

The set of all vertices at distance at most r from a vertex v in a graph G is called an r-ball. We prove that the minimum number of vertices hitting all r-balls in a planar graph G is at most a constant (independent of r) times the maximum number of vertex-disjoint r-balls in G.

Title: Lineup polytopes and exclusion principles

Abstract:

The set of all possible spectra of 1-reduced density operators for systems of N particles on a d-dimensional Hilbert space is a polytope called hypersimplex and this is related to Pauli's exclusion principle. If the spectrum of the original density operators is fixed, the set of spectra (ordered decreasingly) of 1-reduced density operators is also a polytope.

Title: Counting planar maps, 50 years after William Tutte

Abstract:

Every planar map can be properly coloured with four colours. But how many proper colourings has, on average, a planar map with $n$ edges? What if we allow a prescribed number of "monochromatic" edges, the endpoints of which share the same colour? What if we have $q$ colours rather than four?

Title: Polynomial ideals, association schemes, and the Q-polynomial property

Abstract:

Let X ⊆ S^{m−1} be a spherical code in C^m. We study the ideal I ⊆ C[z_1, . . . , z_m] of polynomials that vanish on the points of X: I = { F(z) | (∀a ∈ X) (F(a) = 0) }. The primary example of interest is where the Gram matrix of X is proportional to the first idempotent in some Q-polynomial ordering of an association scheme (X, R) defined on X.