
Discrete Mathematics SeminarWednesdays at 2:00pm in Room 308 Stratton HallWorcester Polytechnic Institute

D TERM 2022C TERM 2022
 Wednesdays 2:002:50pm, Room SH308, Stratton Hall
 16 March: Sheila Sundaram, Pierrepont School "Quasisymmetric functions, descent sets and 0Hecke actions on tableaux"
Zoom Meeting ID: 994 4731 7557
Abstract: I will introduce all the terms in the title, and then survey various bases for the algebra of quasisymmetric functions, and their associated modules for the 0Hecke algebra. I hope to make the talk selfcontained, and time permitting, also hope to report on recent joint work with Elizabeth Niese, Stephanie van Willigenburg, Julianne Vega and Shiyun Wang.
 23 March: Bill Martin, WPI "An introduction to the Paley graphs"
Abstract: Let F_{q} be the finite field of prime power order q. The Paley graph P_{q} has vertex set F_{q} with a directed edge from a to b if ba is a perfect square. I will describe the basic properties of these amazing graphs. For instance, the graph is undirected if and only if q ≡ 1 (mod 4). This is the case we focus on. Here, the graph is strongly regular, giving us one of the simplest examples of a nontrivial association scheme. We fully work out the parameters and eigenvalues of the Paley graph as preparation to focus on their pseudorandom properties.With Ethan Washock in Summer 2021, I was interested in collisions among entrywise products u ∘ v = u' ∘ v' of eigenvectors of the Paley graph and we knew our task would be easier if any three vertices of the graph have a common neighbor. (This is among the most elementary of the pseudorandom properties.) I got stuck on this and Andries Brouwer helped me past a hurdle. I'll explain how we used the Hasse bound on the number of qrational points on an elliptic curve to estimate the number of vertices in the Paley graph at distance h from a, distance i from b, and distance j from c for any three vertices a,b,c. If time permits, I'll show how this relates to my project with Ethan.
30 March: Bill Martin, WPI "Kantor's construction for mutually unbiased bases"
Abstract: This talk introduces mutually unbiased bases; these are collections of measurements of finitedimensional quantum mechanical systems which have numerous applications including quantum cryptography and quantum state tomography.Two unitary bases B and B' for ℂ^{n} are unbiased relative to one another if the Hermitian inner product ❬b,b'❭ has constant modulus as b ranges over vectors in B and b' ranges over vectors in B'. A fundamental question in quantum information theory is "What is the maximum number of pairwise (or mutually) unbiased bases in ℂ^{n}?" It is not hard to show that n+1 is an upper bound on the number of such bases and a collection of n+1 mutually unbiased bases ("MUBs") for ℂ^{n} is said to be complete. Complete sets of MUBs are known whenever n is a prime power and in no other cases. In this talk, I will present a construction of complete sets of MUBs due to Bill Kantor. I will then discuss our attempt to extend this idea to nonprimepower dimensions. I will also mention some joint work with former WPI students on the real case.
 6 April: Guillermo Nuñez Ponasso, WPI "Type II matrices in Association Schemes"
Abstract: A Type II matrix is an n × n matrix M satisfying MM^{()} = n I_{n}, where M^{()} is the Schur inverse of M. These matrices are very interesting in Knot Theory, since some can be used to obtain link invariants. I will present some of the results by Chan and Godsil on the classification of Type II matrices on Strongly Regular Graphs, along with some subsequent work by Munemasa and Ikuta. Then I will present a new construction using the theory of cyclotomy.
 13 April: Miklós Bóna, U. Florida "Superpatterns and superpermutations"
Abstract: At least how long does a permutation have to be if it is to contain all patterns of length k? At least how long does a word over the alphabet {1,2,...,n} have to be if it is to contain all permutations as a subsequence. As a factor? These questions are easy to formulate, but surprisingly difficult to answer, even at the level of bounds. It is quite possible that for some of these questions, the best answers will come from constructions of geometric nature. No previous knowledge of the combinatorics of permutations or pattern avoidance will be assumed.
 20 April: Jessica Wang, WPI "Exploring numerical semigroups through polyhedral geometry"
Abstract: A numerical semigroup is a cofinite subset of the nonnegative integers that is closed under addition and contains zero. The Group cone, C(ℤ_{m}), is a family of rational polyhedra whose congruent integer points are in bijection with numerical semigroups with fixed multiplity. Each face of C(ℤ_{m}) corresponds to a poset that describes the structure of the numerical semigroups found on that face. Interestingly, some faces of C(ℤ_{m}) do not have any integer points on them. In this talk, we present conditions to classify which faces of C(ℤ_{m}) contain integer points by examining their poset.Zoom Meeting ID: 952 4265 8134. For passcode, contact us.
 27 April: Joseph Fehribach, WPI, "The Prime Number Theorem: an overview"
Abstract: The prime number theorem is one of the most famous results in (analytic) number theory.This presentation is a 45minute sketch of an analytic proof.
Meeting ID: 952 4265 8134 Passcode + ZIP code: 483243
 Tuesdays 3:003:50pm, Room SL011, Salisbury Labs
 18 January: No seminar
 25 January: Bill Martin, WPI "A surprising duality property of scaffolds"
Abstract: In this first part of the talk, we present some motivation and the necessary background to present (on February 1st) a proof by Liang, Tan, Tanaka and Wang of a special case of a conjecture I made in 2021 about planar scaffolds for association schemes. The proof is quite technical, involving character theory of finite abelian groups and duality of circular planar graphs.This preparatory talk will review association schemes, important families of examples such as finite groups and distancetransitive graphs, and the structure of BoseMesner algebras. Then we will define scaffolds, review important examples, and present Martin's conjecture (Linear Algebra and its Applications, 2021).
Let X be a finite nonempty set and let Mat_{X}(ℂ) denote the algebra of matrices with rows and columns indexed by the elements of X. Let G=(V(G),E(G)) be a finite digraph with some specified ordered set R ={r_{1}, . . . ,r_{m}}⊆ V(G) of "root nodes" and let w: E(G) → Mat_{X}(ℂ) assign a matric weight to each directed edge of G. Then the scaffold S(G,R;w) is defined to be the sum over all φ :V(G) → X of the tensor φ(r_{1}) ⊗ ⋯ ⊗ φ(r_{m}) weighted by the product of all w(e)_{φ(a),φ(b)} over directed edges e=(a,b) in E(G). While this seems like a mouthful, it captures a number of very natural enumerations of substructures. So the first part will end with examples of scaffolds and their evaluation on coherent algebras and BoseMesner algebras.
 1 February: Rafael Gonzalez D'Leon, Pontificia Universidad Javeriana "Mathematical coincidences: Euler, Catalan, and RNA folding"
Abstract: Posted elsewhere.
 8 February: Bill Martin, WPI "A surprising duality property of scaffolds" (continued)
Abstract: We continue the presentation from January 25, aiming to sketch the proof of the new result of Tan, et al.
 15 February: Duncan Wright, WPI "Putting Errors First  A GraphTheoretic Approach to Quantum Error Correction"
Abstract: We investigate a novel class of quantum error correcting codes to correct errors on both qubits and higherlevel quantum systems represented as qudits, and we develop a graphtheoretic representation for both an arbitrary error set and this new class of reflexive stabilizer codes. In this new framework, we represent the algebraic conditions for error correction in terms of edge avoidance between graphs providing a visual representation of the interplay between errors and error correcting codes. Most importantly, this framework supports the development of quantum codes that correct against a predetermined set of errors, in contrast to current methods. A heuristic algorithm is presented, providing steps to develop codes that correct against an arbitrary noisy channel. We benchmark the correction capability of reflexive stabilizer codes for the case of single qubit errors by comparison to existing stabilizer codes that are widely used. In addition, we present two instances of optimal encodings: a minimal encoding for single qudit errors on a fourstate system, and an optimal encoding for fully correlated noise which achieves a higher encoding rate than previously known. Joint work with Robert Vandermolen.
 22 February: Jessica Wang, WPI "Tiling of Prime and Composite of Kirchhoff Graphs"
Abstract: A Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. We present an algorithm that constructs all Kirchhoff graphs up to a fixed edge multiplicity. We explore the tiling of prime Kirchhoff graphs, specifically, the number of possible prime Kirchhoff graphs given a set of initial fundamental Kirchhoff graphs.
 1 March: Guillermo Nuñez Ponasso, WPI "Small sums of roots of unity"
Abstract: Consider a sum of n kth roots of unity. How small can its absolute value be? We study this problem from different points of view and give bounds using ideas from Diophantine approximation. For the case k=5 we present a novel upper bound involving Lucas numbers. Conjecturally this explains the whole behaviour of minimalnorm sums for the 5^{th} roots of unity.
The chief innovation is the introduction of limit objects for nqueens configurations, which we call queenons. These are a convex set in 𝒫([1/2,1/2]^{2}). We define an entropy function that counts the number of nqueens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of nqueens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.
In combinatorics, objects such as projective planes or designs can be characterized by a matric equation satisfied by the Gram matrix of their incidence matrix. Since this Gram matrix is symmetric, it has an associated quadratic form and the HasseMinkowski theorem applies. In this talk we will go through the basic theory of local fields and quadratic forms, and explain how the HasseMinkowski theorem is applied to obtain nonexistence results in combinatorics, such as the BruckRyserChowla theorem.
Two vectors are combinatorially orthogonal if the size of the intersection of their supports is not 1. An n×n symmetric matrix is combinatorially orthogonal if every pair of rows, or columns, is combinatorially orthogonal. Every orthogonal pair of vectors is combinatorially orthogonal, and every orthogonal matrix is combinatorially orthogonal.
For a graph G, we give a simple structural condition that guarantees the existence of a combinatorially orthogonal matrix M compatible with G. We will see how this connects with work done by Reid and Thomassen on graphs for which every path of length r is contained in a cycle of length s. Finally we discuss implications for characterizing graphs G with q(G)=2.
A TERM 2021To see a list of talks given in this seminar in past years, see this older version
 Mondays 2:002:50pm, in Room 309 Stratton Hall
 30 August: Bill Martin, WPI "Strongly regular graphs and spherical designs"
Abstract: I will give a basic introduction to these two topics we have been studying recently. A strongly regular graph is a regular graph with three distinct eigenvalues. A spherical tdesign is a finite subset of the ddimensional unit sphere which approximates the entire sphere in the sense that the corresponding Riemann sum is exactly equal to the integral of f(x) over the sphere for any polynomial f(x) of degree at most t in d variables.
 6 September: No seminar, Labor Day
 13 September: Benjamin Gobler, WPI "Listing the Rationals using Continued Fractions"
Abstract: It is well known that the rational numbers are countable. From a list which includes each rational number exactly once, we may ask, "What is the 200th rational in the list?" or "Where does 22/7 appear in the list?" To answer these questions, we will explore an original method which uses continued fractions to evaluate and locate terms in the CalkinWilf sequence, one such list of the rationals.
 20 September: Padraig Ó Catháin, WPI "Fischer's proof of Fischer's Inequality"
Abstract: Fischer's Inequality is a standard tool for working with positive definite matrices. In many textbooks (and on Wikipedia) there is a short proof using the square root of a positive definite matrix and the AGM inequality. The original proof is entirely different, and I will present it in its entirety.
 27 September: Ashwin Sah, MIT "Large deviations in random Latin squares"
(This talk will be given over Zoom. Please contact Bill Martin if you wish to receive the Zoom Meeting ID.)
Abstract: We study large deviations of the number N of intercalates (2 x 2 combinatorial subsquares which are themselves Latin squares) in a random n x n Latin square. In particular, for constant δ > 0 we prove that Pr(N ≤ (1δ)n^{2}/4 )≤ exp(Ω(n^{2})) and Pr(N ≥ (1+δ)n^{2}/4 )≤ exp(Ω(n^{4/3}(log n)^{2/3})) both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical ordern Latin square has (1+o(1))n^{2}/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.This work is joint with Matthew Kwan and Mehtaab Sawhney.
 4 October: Mason DiCicco, WPI "The Communication Complexity of Subsequence Detection"
Abstract: The subsequence detection problem is, given a string of length n and a pattern of length k < n, to determine whether the pattern appears in the string as a (notnecessarily contiguous) subsequence. I will give an introduction to the study of Communication Complexity, and prove several bounds with respect to the subsequence detection problem.
 11 October: No seminar.