Seminar

Title: Linear arboricity of sparse multigraphs via orientations

Abstract:

The linear arboricity $la(G)$ of a loopless multigraph $G$ is the minimum number of colors required to edge-color $G$ into linear forests, that is, forests whose components are all paths. The Linear Arboricity Conjecture of Akiyama, Exoo, and Harary asserts that the linear arboricity of a simple graph $G$ is at most $\lceil (\Delta(G)+1)/2 \rceil$.

Title: P-partition power sums

Abstract:

The Hopf algebra of symmetric functions is spanned by several important bases, including by power sum symmetric functions, which encode the class values of the characters of the symmetric group under the Frobenius characteristic map.

Title:  A vertex model for LLT polynomials and k-tilings of the Aztec diamond

Abstract:

We describe a Yang-Baxter integrable colored vertex model, from which we construct a class of partition functions that equal the LLT polynomials of Lascoux, Leclerc, and Thibon. Using the vertex model formalism, we can prove many properties of these polynomials.

Title: Connectivity functions and connectivity intertwining

Abstract:

Connectivity functions provide a nice way of unifying matroid connectivity with various notions of connectivity in graphs. I will present some new and old open problems.

Title: Polynomials, rank and cap sets

Abstract:

In this talk we will look at a variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z_4^n and F_q^n are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets.  We will also mention some further applications of the method, for instance, the solution of the Erdős–Szemerédi theorem sunflower conjecture.

Title: Radical Sylvester-Gallai theorem for cubics - and beyond

Abstract:

In 1893, Sylvester asked a basic question in combinatorial geometry: given a finite set of distinct points $v_1, \ldots, v_m \in \R^N$ such that the line defined by any pair of distinct points $v_i, v_j$ contains a third point $v_k$ in the set, must all points in the set be collinear?

Title: Generalized Subspace Subcode with Application in Cryptology

Abstract:

Most codes with an algebraic decoding algorithm are derived from Reed-Solomon codes. They are obtained by taking equivalent codes, for example Generalized Reed-Solomon codes, or by using the so-called subfield subcode method, which leads to Alternant codes over the underlying prime field, or over some intermediate subfield. The main advantage of these constructions is to preserve both the minimum distance and the decoding algorithm of the underlying Reed-Solomon code.

Title: Algebraic Graph Theory

Abstract:

A graph is distance-regular if we can write the distance adjacency matrices as polynomials in the adjacency matrix. Distance-regular graphs are a class of graphs of significant interest to algebraic graph theorists for their structural and algebraic properties. The notion of distance-regularity can be weakened to a local property on vertices, but when every vertex in the graph is locally distance-regular, the graph will either be distance-regular or in the closely related class of distance-biregular graphs.

Title: On the eigenvalues of the perfect matching derangement graph

Abstract:

The perfect matching derangement graph $M_{2n}$ is defined to be the graph whose vertices are all the perfect matchings of the complete graph $K_{2n}$, and two vertices are adjacent if they contain no common edges. The graph $M_{2n}$ is part of a larger study on the analogs of the Erdős-Ko-Rado theorem, and recently there have been interesting works on $M_{2n}$ and its eigenvalues.

Title: Speeding up Multi-Scalar Multiplication over Fixed Points towards Efficient zkSNARKs

Abstract:

The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in pairing-based trusted setup zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs), thus fast algorithms of MSM over fixed points are desirable for practical applications.