��ݮ��Ƶ

Title:Splitting algorithms for monotone inclusions with minimal��dimension

Abstract: Many situations in convex optimization can be modeled as the problem of��finding a zero of a monotone operator, which can be regarded as a��generalization of the gradient of a differentiable convex function. In��order to numerically address this monotone inclusion problem, it is��vital to be able to exploit the inherent structure of the operator��defining it. The algorithms in the family of the splitting methods��achieve this by iteratively solving simpler subtasks that are defined by��separately using some parts of the original problem.

In the first part of this talk, we will introduce some of the most��relevant monotone inclusion problems and present their applications to��optimization. Subsequently, we will draw our attention to a common��anomaly that has persisted in the design of methods in this family: the��dimension of the underlying space —which we denote as lifting— of the��algorithms abnormally increases as the problem size grows. This has��direct implications on the computational performance of the method as a��result of the increase of memory requirements. In this framework, we��characterize the minimal lifting that can be obtained by splitting��algorithms adept at solving certain general monotone inclusions.��Moreover, we present splitting methods matching these lifting bounds, and thus��having minimal lifting.

��

Title:A Toric Analogue for Greene's Rational Function of a Poset

Abstract: Given a finite poset, Greene introduced a rational function obtained by summing certain rational functions over the linear extensions of the poset. This function has interesting interpretations, and for certain families of posets, it simplifies surprisingly. In particular, Greene evaluated this rational function for strongly planar posets in his work on the Murnaghan–Nakayama formula. Develin, Macauley, and Reiner introduced toric posets, which combinatorially are equivalence classes of posets (or rather acyclic quivers) under the operation of flipping maximum elements into minimum elements and vice versa. In this work, we introduce a toric analogue of Greene's rational function for toric posets, and study its properties. In addition, we use toric posets to show that the Kleiss–Kuijf relations, which appear in scattering amplitudes, are equivalent to a specific instance of Greene's evaluation of his rational function for strongly planar posets. Also in this work, we give an algorithm for finding the set of toric total extensions of a toric poset.

Title:Shifted Parking function

Abstract:Stanley recently introduced the shifted parking function symmetric function as a shifted analogue of the parking function symmetric function and posed the question of what the corresponding combinatorial objects are. This talk will answer that question and explain how the answer connects to projective representations of the symmetric group. Based on joint work with Zach Hamaker.

Title:��A hereditary generalization of Nordhaus-Gaddum graphs

Abstract:��This talk will be an expanded version of the speaker's CanaDAM talk, the abstract of which is as follows:

Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph G and its complement is at most |G| + 1. The Nordhaus-Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy that the sum of the chromatic numbers of H and its complement are at least |H|. We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss chi-boundedness and algorithmic results.

Title:Unsplittable Multicommodity Flows in Outerplanar Graphs

Abstract:

Given a graph G with edge capacities and multiple source-sink pairs, each with an associated demand, the multicommodity flow problem consists of routing all demands simultaneously without violating edge capacities. The graph obtained by including an edge (s_i,t_i) for a demand with source-sink s_i,t_i is called the demand graph H.

A multicommodity flow is called unsplittable if all the flow between a source-sink pair is routed along a single path. In general, existence of a feasible (fractional) flow does not imply the existence of an unsplittable flow, even in very simple settings. ��This leads to a natural question: given a feasible flow, does there exist an unsplittable flow which satisfies all the demands and violates the edge capacities (in an additive sense) by at most a small factor times the value of the maximum demand Dmax?��

Dinitz, Garg and Goemans proved that in the single-source setting (i.e., when H is a star), any feasible fractional flow can be converted into an unsplittable flow that violates the edge capacities by no more than Dmax.��

The problem is significantly less understood when the demand graph H is arbitrary. Schrijver, Seymour and Winkler��proved that if G is a cycle, then any feasible multicommodity flow can be converted into an unsplittable one that violates the edge capacities by at most 3Dmax/2. Before our work, cycles were the only known nontrivial class of graphs for which an unsplittable flow was guaranteed to exist, incurring at most an additive O(Dmax) violation of edge capacities, whenever a feasible flow existed. In this talk, I will discuss how to extend this result to the class of outerplanar graphs.

This is a joint work with Nikhil Kumar.

Title:Regularity lemmas for hypergraphs of bounded VC dimension: improved bounds

Abstract:An important result at the interface of graph theory and logic is that graphs of bounded VC dimension have (small) homogeneous vertex-partitions, i.e., partitions where almost every pair of parts has density close to 0 or 1. Recently, Chernikov and Towsner proved a hypergraph generalization of this fact. The quantitative aspects of their result remain open. I will present some recent progress on this problem, answering two questions of Terry. This is a joint work with Asaf Shapira and Yuval Wigderson.

��

Title:��A Sudoku Baranyai's Theorem

Abstract: Motivated by constructing higher dimensional Sudokus we generalize the famous Baranyai's theorem. Let$n=\prod_{i=1}^d a_i$. Suppose that an $n\times\dots \times n$ ($d$ times) array $L$ is partitioned into$n/a_1\times\dots\times n/a_d$ sub‐arrays (called blocks). Can we color the $n^d$ cells of $L$ with $n^{d21}$ colors so that each layer (obtained by fixing one coordinate) and each $n/a_1\times\dots\times n/a_d$block contains each color exactly once? We generalize the well‐know theorem of Baranyai to answer this queestion. The case $d=2 a_1=a_2=3$ corresponds to the usual Sudoku. We also provide finite fieldconstruction of various related objects. This is joint work with Sho Suda.

Title:��Refuting semirandom CSPs via spectral graph theory techniques

Abstract:

: In this talk, we will consider recent spectral techniques, developed by [HKM23] and [GKM22], for combinatorial and algorithmic problems. We shall focus, in particular, on designing algorithms for refuting semirandom instances of constraint satisfaction problems. The main component of the talk is a reduction to studying spectral properties of so-called "Kikuchi graphs" corresponding to a system of homogeneous degree-q multilinear polynomials.

No prerequisites in spectral graph theory beyond basic linear algebra are��assumed.

[HKM23]: A simple and sharper proof of the hypergraph Moore bound

[GKM22]: Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"

Title:The external activity complex of a pair of matroids

Abstract: In 2016, Ardila and Boocher were investigating the variety obtained by taking the closure of a linear space within A^n in its compactification (P^1)^n; later work named this the "matroid Schubert variety". Its Gröbner degenerations led them to define, and study the commutative algebra of, the _external activity complex_ of a matroid. If the matroid is on n elements, this is a complex on 2n vertices whose facets encode the external activity of bases.

In recent work with Andy Berget on Speyer's g-invariant, we required a generalisation of the definition of external activity where the input was a pair of matroids on the same ground set. We generalise many of the results of Ardila--Boocher to this setting. Time permitting, I'll also present the tropical intersection theory machinery we use to understand the external activity complex of a pair.

For those who attended my talk at this year's CAAC on this paper, the content of the present talk is meant to be complementary.

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

Title:��2-Y-homogeneous��distance-biregular��graphs

Abstract:��Distance-biregular graphs (DBRGs) generalize distance-regular graphs by admitting a bipartition of the vertex set, where each part satisfies local distance-regularity ��under distinct intersection arrays. In recent years, a particular subclass of these graphs, those satisfying the so-called��2-Y-homogeneous condition, has garnered increasing attention due to its rich connections with combinatorial design theory and the representation theory of Terwilliger algebras. In this talk, we will examine the key structural conditions that characterize��2-Y-homogeneous DBRGs. We will survey recent progress in their classification under various combinatorial constraints, highlighting both known results and open problems.