 # Discrete Mathematics Seminar

## Wednesdays at 2:00pm in Room 308 Stratton Hall

#### Discrete Math Seminar Schedule for Spring 2022:

D TERM 2022

• Wednesdays 2:00-2:50pm, Room SH308, Stratton Hall

• 16 March: Sheila Sundaram, Pierrepont School "Quasisymmetric functions, descent sets and 0-Hecke 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 0-Hecke algebra. I hope to make the talk self-contained, 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 Fq be the finite field of prime power order q. The Paley graph Pq has vertex set Fq with a directed edge from a to b if b-a 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 non-trivial 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 q-rational 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 finite-dimensional 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 inn?" 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 non-prime-power 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 In, 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 non-negative 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.

• 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 45-minute sketch of an analytic proof.

Meeting ID: 952 4265 8134 Passcode + ZIP code: 483243

C TERM 2022

• Tuesdays 3:00-3: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 distance-transitive graphs, and the structure of Bose-Mesner 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 non-empty set and let MatX(ℂ) 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 ={r1, . . . ,rm}⊆ V(G) of "root nodes" and let w: E(G)MatX(ℂ) 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 φ(r1) ⊗ ⋯ ⊗ φ(rm) 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 Bose-Mesner 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 Graph-Theoretic Approach to Quantum Error Correction"
Abstract: We investigate a novel class of quantum error correcting codes to correct errors on both qubits and higher-level quantum systems represented as qudits, and we develop a graph-theoretic 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 four-state 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 k-th 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 minimal-norm sums for the 5th roots of unity.

## Previous Semesters

B TERM 2021

• Tuesdays 3:00-3:50pm, Room SL402, Salisbury Labs

• 26 October: Michael Simkin, Harvard "The number of n-queens configurations"
Abstract: The n-queens problem is to determine 𝒬(n), the number of ways to place n mutually non-threatening queens on an n×n board. We show that there exists a constant α= 1.942 ± 3 ×10-3 such that 𝒬(n) = ((1 ± o(1))ne)n. The constant α is characterized as the solution to a convex optimization problem in 𝒫([-1/2,1/2]2), the space of Borel probability measures on the square.

The chief innovation is the introduction of limit objects for n-queens 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 n-queens 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 n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons.

• 2 November: No seminar

• 9 November: Guillermo Nuñez Ponasso, WPI "The Hasse-Minkowski Theorem in Combinatorics"
Abstract: The Hasse-Minkowski theorem states that given a quadratic form f with rational coefficients, f has rational zeroes if and only if f has zeroes in every completion of the rationals. This result can be used to characterize quadratic forms on the rationals up to equivalence.

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 Hasse-Minkowski theorem applies. In this talk we will go through the basic theory of local fields and quadratic forms, and explain how the Hasse-Minkowski theorem is applied to obtain non-existence results in combinatorics, such as the Bruck-Ryser-Chowla theorem.

• 16 November: Brendan Rooney, RIT "Combinatorial Orthogonality and the Inverse Eigenvalue Problem for Graphs"
Abstract: The inverse eigenvalue problem for graphs asks: given a graph G, what spectra are realizable from its vertex and edge-weightings? The parameter q(G) is the smallest number of distinct eigenvalues over all matrices M compatible with G (i.e., the off-diagonal zero pattern of M is the same as A(G)).

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.

• 23 November: Thanksgiving Week No seminar.

• 30 November: Brigitte Servatius, WPI
"Chebychev said, and I say it again:
There is always a prime between n and 2n."
Abstract: As an "advertisement" of Chvatal's new book : "The discrete mathematical charms of Paul Erdos" we will present Paul Erdos' proof of Bertrand's Postulate and compare it to earlier proofs, as laid out in the first chapter of Chvatal's book.

• 7 December: Nikolaos Kalampalikis, WPI "A graph theoretic proof for the Sensitivity Conjecture"
Abstract: The Sensitivity Conjecture has been important problem in theoretical computer science. In this presentation, we will go over Huang's proof of showing that every (2n-1 +1)-vertex induced subgraph of the n-dimensional cube graph has maximum degree of at least √n. As a direct consequence we will show that sensitivity and degree of a boolean function are polynomially related.

A TERM 2021

• Mondays 2:00-2: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 t-design is a finite subset of the d-dimensional 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 Calkin-Wilf 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"