Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Select All
Limit to events tagged with one or more of:
Select All
Limit to events where the audience is one or more of:
Select All
Friday, January 24, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Jim Geelen

Title: Well-quasi-ordering and connectivity

Speaker: Jim Geelen
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Connectivity systems provide an abstract framework for studying various connectivity notions on graphs, matroids, and other combinatorial structures. In joint work with Rutger Campbell, we prove a novel well-quasi-ordering result on certain connectivity systems which gives new excluded minor results in matroid theory and gives new proofs for several results in graph theory.

 

 

Thursday, January 30, 2025 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and enumerative combinatorics seminar-Nantel Bergeron

Title: Equivariant quasisymmetry

Speaker Nantel Bergeron
Affiliation York University
Location MC 5479

 Abstract: We introduce equivariant quasisymmetry, a version of quasisymmetry for polynomials in two sets of variables. Using this definition we define double fundamental polynomials and double forest polynomials, a quasisymmetric generalizations of the theory of double Schur and double Schubert polynomials, where the subset of noncrossing permutations play the role of $S_n$.This combinatorics is governed by the quasisymmetric flag variety, a new geometric construction which plays the role for equivariant quasisymmetry what the usual flag variety plays in the classical story.

In this talk, I will focus on the combinatorial aspect first, and with the remaining time discuss the geometrical implications.

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

Friday, January 31, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Jane Gao

Title:Evolution of random graph orders and their dimensions

Speaker: Jane Gao
Affiliation: University of Waterloo
Location: MC 5501

Abstract: A poset is a set X equipped with a partial order. In this talk I will briefly review the literature of different models on random orders. Then we discuss a particular model called the random graph order. The random graph order is classical model to generate a random causal set, which was introduced in physics to model and analyse the space-time universe. 

We will focus on an open problem proposed by Erdos, Kierstad and Trotter on the evolution of the dimensions of random graph orders. This problem has been studied by Albert and Frieze, and by Erdos, Kierstad and Trotter around 1990. Better bounds on the dimensions were obtained by Bollobas and Brightwell in 1997, for “non-sparse” random graph orders. We study the last piece of the puzzle, in the bipartite case, by investigating “a transition phase” that was predicted to occur in the sparse regime by Bollobas and Brightwel, and we prove a negative result to their prediction. We expect that a similar phenomenon would occur in the nonbipartite case.

This talk is based on a collaborated work with Arnav Kumar. 

 

 

Monday, February 3, 2025 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory-Shlomo Hoory

Title: Entropy and the growth rate of universal covering trees

Speaker: Shlomo Hoory
Affiliation: Tel-Hai College
Location: Please contact Sabrina Lato for Zoom link.

Abstract:This work studies the relation between two graph parameters, rho and Lambda. For an undirected graph G,  rho(G) is the growth rate of its universal covering tree, while Lambda(G) is a weighted geometric average of the vertex degree minus one, corresponding to the rate of entropy growth for the non-backtracking random walk (NBRW). It is well known that rho >= Lambda for all graphs, and that graphs with rho = Lambda exhibit some special properties. In this work we derive an easy to check, necessary and sufficient condition for the equality to hold. Furthermore, we show that the variance of the number of random bits used by a length l NBRW is O(1) if rho = Lambda and Omega(l) if rho > Lambda. As a consequence we exhibit infinitely many non-trivial examples of graphs with rho = Lambda.

Joint work with Idan Eisner, Tel-Hai College, Israel.

Thursday, February 6, 2025 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and enumerative combinatorics seminar-Hunter Spink

Title: New perspectives on quasisymmetry via divided differences, flag varieties, etc.

Speaker Hunter Spink
Affiliation UofT
Location MC 5479

 Abstract: In this talk we will introduce a new combinatorial approach to understanding quasisymmetric polynomials via a quasisymmetric analogue of "divided differences". The resulting combinatorial theory is paired with a geometric theory that closely follows the classical development of Schubert calculus and Schubert varieties. Next week Nantel Bergeron will continue with the torus-equivariant story.

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

Friday, February 7, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Levent Tuncel

Title: A New Complexity Analysis of Primal-Dual Interior-Point Methods with Applications to Hyperbolic Cone Programming

Speaker: Levent Tuncel
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Primal-dual interior-point methods stand at the forefront of convex optimization, distinguished by their theoretical efficiency and practical robustness. After presenting the fundamental 
structure of these algorithms, I will introduce a complexity measure for a large family of primal-dual algorithms. A consequence of the new analyses of this complexity measure is a substantial improvement of the iteration 
complexity bounds for these primal-dual algorithms on hyperbolic cone programming problems.

This talk is based on joint work with Joachim Dahl and Lieven Vandenberghe.

 

 

Monday, February 10, 2025 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory-Antonina P. Khramova

Title: : Algebraic bounds for sum-rank-metric codes

Speaker: Antonina P. Khramova
Affiliation: Eindhoven University of Technology
Location: Please contact Sabrina Lato for Zoom link.

Abstract:The sum-rank metric is a generalization of the well-known Hamming and rank metrics. In this talk we introduce two new bounds on the maximal cardinality of the sum-rank-metric code with a given minimum distance. One of the bounds exploits a connection between such a code and a (d-1)-independent set in a graph defined for the sum-rank-metric space. We then use the eigenvalues of the graph to deduce the bound. The second bound is derived from the Delsarte's LP method, which has been previously obtained for Hamming metric, rank metric, Lee metric, and others, but the sum-rank-metric case remained open. To derive the new LP bound we propose a way to construct an association scheme for the sum-rank metric, since the approach used in the Hamming and the rank-metric cases fails due to the associated graph not being distance-regular in general. Based on computational experiments on relatively small instances, we observe that the obtained bounds often outperform the bounds previously known for sum-rank-metric codes.

This talk is based on a joint work with A. Abiad, A.L. Gavrilyuk, A. Ravagnani, and I. Ponomarenko.

Tuesday, February 11, 2025 3:00 pm - 4:00 pm EST (GMT -05:00)

Graphs and Matroids - Seokbeom Kim

Title: Structure of tournaments with a forbidden subtournament

Speaker: Seokbeom Kim
Affiliation: KAIST
Location: MC 5479

Abstract: For a tournament $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that the complete structure of $S$-free tournaments is known. 

Let $\triangle(1, 2, 2)$ be a tournament obtained from the cyclic triangle by substituting two-vertex tournaments for two of its vertices. In this talk, we present a structure theorem for $\triangle(1, 2, 2)$-free tournaments, which was previously unknown. As an application, we provide tight bounds for the chromatic number as well as the size of the largest transitive subtournament for such tournaments.

This talk is based on joint work with Taite LaGrange, Mathieu Rundström, Arpan Sadhukhan, and Sophie Spirkl.

Thursday, February 13, 2025 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and enumerative combinatorics seminar-Yasaman Yazdi

Title: Statistical Fluctuations in the Causal Set-Continuum Correspondence

Speaker Yasaman Yazdi
Affiliation Dublin Institute for Advanced Studies and Perimeter Institute
Location MC 5479

 Abstract: Causal set theory is an approach to quantum gravity that proposes that spacetime is fundamentally discrete and the causal relations among the discrete elements play a prominent role in the physics. Progress has been made in recognizing and understanding how some continuumlike features can emerge from causal sets at macroscopic scales, i.e., when the number of elements is large. An important result in this context is that a causal set is well approximated by a continuum spacetime if there is a number-volume correspondence between the causal set and spacetime.

This occurs when the number of elements within an arbitrary spacetime region is proportional to its volume. Such a correspondence is known to be best achieved when the number of causal set elements is randomly distributed according to the Poisson distribution. I will discuss the Poisson distribution and the statistical fluctuations it induces in the causal set-continuum correspondence, highlighting why it is important and interesting. I will also discuss new tools and techniques that facilitate such analyses.

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

Friday, February 14, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Xi He

Title:Accuracy Aware Minimally Invasive Data Exploration For Decision Support

Speaker: Xi He
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Decision-support (DS) applications, crucial for timely and informed decision-making, often analyze sensitive data, raising significant privacy concerns. While privacy-preserving randomized mechanisms can mitigate these concerns, they introduce the risk of both false positives and false negatives. Critically, in DS applications, the number of false negatives often needs to be strictly controlled. Existing privacy-preserving techniques like differential privacy, even when adapted, struggle to meet this requirement without substantial privacy leakage, particularly when data distributions are skewed. This talk introduces a novel approach to minimally invasive data exploration for decision support. Our method minimizes privacy loss while guaranteeing a bound on false negatives by dynamically adapting privacy levels based on the underlying data distribution. We further extend this approach to handle complex DS queries, which may involve multiple conditions on diverse aggregate statistics combined through logical disjunction and conjunction. Specifically, we define complex DS queries and their associated accuracy requirements, and present algorithms that strategically allocate a privacy budget to minimize overall privacy loss while satisfying the bounded accuracy guarantee.