Friday, December 15, 2023 3:30 PM EST

Title: Online edge colouring

Speaker: David Wajc
Affiliation: Technion — Israel Institute of Technology
Location: MC 5501

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.

Friday, December 8, 2023 3:30 PM EST

Title: Nash-Williams Orientation for Infinite Graphs

Speaker: Amena Assem Abd-AlQader Mahmoud
Affiliation: University of Waterloo
Location: MC 5501

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.

Friday, December 8, 2023 1:00 PM EST

Title: Prophets, philosophers, and online algorithms

Speaker: David Wajc
Affiliation: Technion
Location: MC 6029

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.

Thursday, December 7, 2023 3:00 PM EST

Title: The Container method for Enumerating Triangle-free graphs

Speaker: Amitha Vallapuram
Affiliation: University of Waterloo
Location: MC 5417

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 K3 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.

Monday, December 4, 2023 11:30 AM EST

Title:  A threshold for fractional Sudoku completion

Speaker: Peter Dukes
Affiliation: University of Victoria
Location: Please contact Sabrina Lato for Zoom link.

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.

Friday, December 1, 2023 3:30 PM EST

Title: Wires, bits, and the cost of sorting

Speaker: Samuel Jaques
Affiliation: University of Waterloo
Location: MC 5501

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?

Friday, December 1, 2023 1:00 PM EST

Title: Sublinear Regret 101

Speaker: Nathan Benedetto Proenca
Affiliation: University of Waterloo
Location: MC 6029

Abstract: The purpose of this talk is to look at specific algorithms for online convex optimization attaining sublinear regret. In this way, we can get more familiar with the online learning setup and with the ingredients necessary to attain sublinear regret.

Thursday, November 30, 2023 2:00 PM EST

Title: Polarization operators in superspace

Speaker: Kelvin Chan
Affiliation: York University
Location: MC 6029

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

Abstract: The classic coinvariant space is a graded representation of the symmetric group with deep connections to permutation statistics and Hall-Littlewood polynomials. Its generalization, the diagonal harmonics, has a rich connection to Macdonald polynomials and the q,t-Catalan numbers. In this talk, we consider the variant of the classical coinvariant story in the superspace. We briefly survey its connections and recent developments. We introduce polarization operators and discuss a new basis for its alternating component. We also discuss a folklore on cocharge and propose a basis for the super harmonics.

Monday, November 27, 2023 11:30 AM EST

Title: On the intersection density of transitive groups with degree 3p

Speaker: Sarobidy Razafimahatratra
Affiliation: University of Primorska
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, a subset $\mathcal{F}\subset G$ is intersecting if any two elements of $\mathcal{F}$ agree on some elements of $\Omega$. The \emph{intersection density} of $G$ is the rational number $\rho(G)$ given by the maximum ratio $\frac{|\mathcal{F}|}{|G|/|\Omega|}$, where $\mathcal{F}$ runs through all intersecting sets of $G$.

Most results on the intersection density focus on particular families of transitive groups. One can look at problems on the intersection density from another perspective. Given an integer $n\geq 3$, we would like to determine the possible intersection densities of transitive groups of degree $n$. This problem turns out to be extremely difficult even in the case where $n$ is a product of two primes.

Friday, November 24, 2023 3:30 PM EST

Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

Speaker: Karen Yeats
Affiliation: University of Waterloo
Location: MC 5501

Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.

Friday, November 24, 2023 1:00 PM EST

Title: Online Convex Optimization

Speaker: Victor Sanches Portella
Affiliation: University of British Columbia
Location: MC 6029

Abstract: Online learning (OL) is a theoretical framework for learning with data online. Moreover, we usually make no assumptions on the distribution of the data, allowing it even to be adversarial to the learner. Maybe surprisingly, we can still design algorithms that, in some sense, “successfully learn” in this setting. This level of generality makes many of the ideas, algorithms, and techniques from OL useful in applications in theoretical computer science, optimization in machine learning, and control. In this talk I will give a brief introduction to the key concepts in online learning and  mention a few topics within or adjacent to online learning that I believe cover fundamental ideas in OL and/or with interesting open research questions.

Thursday, November 23, 2023 3:00 PM EST

Title: Several Gyrafas-Sumner-type results for treewidth

Speaker: Sepehr Hajebi
Affiliation: University of Waterloo
Location: MC 5417

Abstract: For a graph parameter which goes unbounded at both ends of a robust sparsity spectrum, one naturally asks if it is bounded anywhere in the middle. This is modelled after a well-known conjecture of Gyarfas and Sumner, asking the above question for the chromatic number as the parameter and the girth as the measure of sparsity. We look through this lens at the treewidth as the parameter and present a number of recent results answering the corresponding question in various settings. If time permits, we’ll try to sketch a proof as well as some directions for future work.

This is joint work with Bogdan Alecu, Maria Chudnovsky, Sophie Spirkl and partly with Tara Abrishami.

Thursday, November 23, 2023 2:00 PM EST

Title: Filtered deformations of commutative algebras

Speaker: Jason Bell
Affiliation: University of Waterloo
Location: MC 6029

Note: There will be no pre-seminar.

Abstract: We’ll look at different ways of deforming the multiplicative structure of “classical” algebras to obtain new algebras and explain how this algebraic structure can often be understood combinatorially.  We’ll then look at a special class of algebras one can produce this way called filtered deformations and we’ll discuss a conjecture of Etingof which asserts that in positive characteristic that filtered deformations of commutative rings should be in some natural sense very close to being commutative themselves. Not much background will be assumed.

Monday, November 20, 2023 11:30 AM EST

Title: Quantum Automorphism Groups of Trees

Speaker: Prem Nigam Kar
Affiliation: Technical University of Denmark
Location: Please contact Sabrina Lato for Zoom link.

Abstract: We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum version of Jordan’s theorem for the automorphism groups of trees. This is one of the first characterisations of quantum automorphism groups of a natural class of graphs with quantum symmetry. This talk is based on the following preprint: https://arxiv.org/abs/2311.04891

Friday, November 17, 2023 3:30 PM EST

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

Speaker: Luke Postle
Affiliation: University of Waterloo
Location: MC 5501

Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Friday, November 17, 2023 1:00 PM EST

Title: Multiplicative Weight Update (MWU) Method for Solving Packing/Covering LPs

Speaker: Sepehr Assadi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: I will present an overview of the MWU technique for solving Packing/Covering LPs easily and efficiently. The talk will be based on a combination of results from the following resources: (1) https://epubs.siam.org/doi/pdf/10.1137/1.9781611976014.11 (2) https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Thursday, November 16, 2023 2:00 PM EST

Title: Linear relations and Lorentzian property of chromatic symmetric functions

Speaker: Alejandro Morales Borrero
Affiliation: Université du Québec à Montréal
Location: MC 6029

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

Abstract: The chromatic symmetric function (CSF) of Dyck paths of Stanley and its Shareshian Wachs q-analogue (q-CSF) have important connections to Hessenberg varieties, diagonal harmonics and LLT polynomials. In the, so called, abelian case they are related to placements of non-attacking rooks by results of Stanley-Stembridge (1993) and Guay-Paquet (2013).

Monday, November 13, 2023 11:30 AM EST

Title: Distance-regular graphs that support a uniform structure

Speaker: Roghayeh Maleki
Affiliation: University of Primorska
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Given a connected bipartite graph $G$, the adjacency matrix $A$ of $G$ can be decomposed as  $A=L+R$, where $L=L(x)$ and $R=R(x)$ are respectively the  lowering and the raising matrices with respect to a certain vertex $x$. The graph $G$ has a \textit{uniform structure} with respect to $x$ if the matrices $RL^2$, $LRL$, $L^2R$, and $L$ satisfy a certain linear dependency.

Friday, November 10, 2023 3:30 PM EST

David B. Shmoys

Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics

Speaker: David B. Shmoys
Affiliation: Cornell University
Location: MC 5501

Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.

Thursday, November 9, 2023 3:00 PM EST

Title: The Tutte Polynomial, Bipartite Representations of Graphs, and Grid Walking 

Speaker: Josephine Reynes
Affiliation: University of Waterloo
Location: MC 5417

Abstract:  The Tutte Polynomial has many equivalent definitions. It can be defined by a deletion-contraction relation with the terms determined by the sequence of contractions, deletions, loops, and isthmi. This definition is independent of edge order. Another definition relies on a fixed edge ordering and examines the edge activities over maximal spanning forests. There is a direct relationship between edge activity and deletion/contraction for a given edge ordering. Furthermore, the monomials of the Tutte polynomial can be interpreted as grid walks. This allows for an approach to the Tutte polynomial on hypergraphs by examining the grid walks of the bipartite representation of the graph.

Thursday, November 9, 2023 2:00 PM EST

Title: Extended Schur Functions and Bases Related by Involutions

Speaker: Spencer Daugherty
Affiliation: North Carolina State University
Location: MC 6029

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

Abstract: The extended Schur basis and the shin basis generalize the Schur functions to the dual algebras of the quasisymmetric functions and the noncommutative symmetric functions. We define a creation operator and a Jacobi-Trudi rule for certain shin functions and show that a similar matrix determinant expression does not exist for every shin function.

Monday, November 6, 2023 11:30 AM EST

Title: Kemeny’s constant and random walks on graphs

Speaker: Jane Breen
Affiliation: Ontario Tech University
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Kemeny's constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are. This comes to the forefront when the Markov chain in question is a random walk on a graph, in which case Kemeny's constant is interpreted as a measure of how `well-connected' the graph is. Though it was first introduced in the 1960s, interest in this concept has recently exploded. This talk will provide an introduction to Markov chains, an overview of the history of Kemeny’s constant, discussion of some applications, and a survey of recent results, with an emphasis on those that are extensions or generalizations of simple random walks on graphs, to complement Sooyeong’s talk from two weeks ago.

Friday, November 3, 2023 3:30 PM EDT

Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Speaker: Walaa Moursi
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Thursday, November 2, 2023 2:00 PM EDT

Title: Snake decompositions of lattice path matroids

Speaker: Jerónimo Valencia-Porras
Affiliation: University of Waterloo
Location: MC 6029

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

Abstract: We study Ehrhart theory of lattice path matroid polytopes motivated by a conjecture by De Loera, Haws and Köppe. More specifically, we aim to understand the h*-vector of this family of matroid polytopes. To do so, we subdivide them into smaller matroid polytopes such that each piece is a snake, which are matroids such that their matroid polytope coincides with the order polytope of a fence poset.

Monday, October 30, 2023 11:30 AM EDT

Title: Graphs that Admit Orthogonal Matrices

Speaker: Shaun Fallat
Affiliation: University of Regina
Location: Please contact Sabrina Lato for Zoom link.

Abstract: Given a simple graph $G=(\{1,\ldots, n},E), we consider the class $S(G)$ of real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}\neq 0$ iff $ij \in E$. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), $q(G)$ - known as the minimum number of distinct eigenvalues of $G$ - has emerged as one of the most well-studied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.

Pages

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2023 (147)
    1. December (7)
    2. November (17)
    3. October (14)
    4. September (10)
    5. August (7)
    6. July (19)
    7. June (21)
    8. May (12)
    9. April (5)
    10. March (17)
    11. February (10)
    12. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)