
Discrete Mathematics SeminarMondays at 4:00pm in Room 202 Stratton HallWorcester Polytechnic Institute

C TERM 2023
 Mondays 4:004:50pm, Room SH202, Stratton Hall
 16 January: No seminar (MLK Day)
 23 January: Brigitte Servatius, WPI, "Selfdual maps on the sphere and other compact surfaces"
Abstract: TBD
 30 January: No seminar, take a break
Abstract: TBD
 6 February: Bill Martin, WPI, "Dispersed graph labellings"
Abstract: I will discuss a fun problem that I recently worked on with Doug Stinson (Waterloo). Let G be a graph with vertex set V and pathlength distance function d(.,.). A kdispersed labeling of G is a linear ordering v_{1}, v_{2}, ..., v_{n} of the vertices such that d(v_{i1}, v_{i} ) ≥ k for all i=2,...,n. Finding the best k for a given graph is an NPhard problem but we have bounds and can find exact values for various families of graphs. I predict you can do better than I have done.
 13 February: Brigitte Servatius, WPI, "Delta matroids"
Abstract: They were invented by Andre Bouchet in 1987. We will go over their definition, explain why they are not matroids and use maps of graphs on surfaces as source of examples.
 20 February: Neranga Fernando, College of the Holy Cross, "Quandles, racks and shelves"
Abstract: A quandle is a set X with a binary operation ∗ : X × X → X satisfying:The three axioms of a quandle algebraically encode the three Reidemeister moves in knot theory.
 For all x ∈ X, x ∗ x = x
 For all y ∈ X, the map β_{y} : X → X defined by β_{y}(x)= x ∗ y is invertible.
 For all x,y,z ∈ X, (x ∗ y) ∗ z = (x ∗ z) ∗ (y ∗ z).
A rack is a set with a binary operation that satisfies (ii) and (iii), and a shelf is a set with a binary operation satisfying selfdistributivity (iii).
I will begin this talk by giving an introduction to quandles. I will then talk about racks, shelves and quandle rings. Moreover, I will talk about a recent joint work with Matthew Pradeep Goonewardena and Mohamed Elhamdadi on shelves.
 27 February: Speaker TBD, "Title TBA"
Abstract: TBD
A TERM 2022
 Wednesdays 3:003:50pm, Room SH106, Stratton Hall
 31 August: Bill Martin, WPI, "Discovering new strongly regular graphs"
Abstract: Can you construct a regular graph in which any two vertices have a unique common neighbor? How about a regular graph where any two vertices have λ > 1 common neighbors? What if we require λ triangles on each edge and λ+1 common neighbors for any two unequal nonadjacent vertices? Any connected graph with such regularity is strongly regular: it must be a regular graph with three distinct eigenvalues. Some rather small open problems in this area remain unsolved. (For example, a famous problem of John Conway asks if a 14regular graph exists in which each edge lies in a unique triangle and each pair of nonadjacent vertices are the corners of a unique quadrilateral.)Until a few years ago, the smallest open parameter set for a strongly regular graph was (65,32,15,16): is there a 32regular graph on 65 vertices in which each pair of adjacent (resp., nonadjacent, distinct) vertices have 15 (resp., 16) common neighbors? In a sense, this would resemble a "finite field" of order 65. Oleg Gritsenko produced such a graph in October 2020 and this is our point of departure. Inspired by Gritsenko, Jason Williford concocted a general recipe for strongly regular graphs of valency k on 2k+1 vertices. The Paley graph of any finite field gives an example. But we found more. I will describe our approach, the examples we found, and the many remaining open questions.
The talk should be accessible to advanced undergraduate students.
 7 September: Cristina Ballantine, College of the Holy Cross, "Hooks and contents in partitions"
Abstract: The irreducible polynomial representations of the general linear group are indexed by partitions. The dimension of a representation is given by a formula involving the hook lengths and the contents of cells in the Young diagram of the indexing partition. There are also analogous formulas for irreducible polynomial representations of symplectic and orthogonal groups. I will discuss the combinatorial nature of identities involving the symplectic and orthogonal hookcontent formulas. These have been conjectured by T. Amdeberhan. Time permitting, I will also introduce some auxiliary results. No knowledge of partition theory is required. I will introduce all notions discussed. The representation theory is mentioned only as motivation and I will not discuss it further in the talk. (Joint work with Tewodros Amdeberhan and George Andrews.)
 14 September: Adam Zsolt Wagner, WPI, "Title"
Abstract:
 21 September: Guillermo Nuñez Ponasso, WPI, "Title"
Abstract:
 28 September: Mason DiCicco, Department of Computer Science, WPI, "Expected length of the longest common subsequence"
Abstract: Given two random binary sequences of length n, what is L(n), the expected length of their longest common subsequence? Chvátal and Sankoff (1975) proved that L(n) is asymptotically equal to γn for some constant γ (which we call the Chvátalâ€“Sankoff constant). However, the exact value of γ is still unknown. (The best bounds are 0.788 < γ < 0.826 due to Lueker (2009).) In this talk I will describe the general method used to calculate upper bounds for γ.
 5 October: Bill Martin, WPI, "Synchronization and designs in the symmetric group"
Abstract: Entering the maze, you will be randomly placed in one of these eight rooms. The rooms all look identical to one another; each room has four exit doors: Red, Blue, Green, and White. The White door exiting Room 1 leads to safety while the White door in each other room leads to certain death. Can you find your way to safety?
You don't know where you will start  and you can't see what room you are in at any point in time  yet you want to specify a word in the alphabet {R, B, G} which will bring you to Room 1: you want to be certain that, after you follow directions, choosing doors according to this word, youâ€™ll finish in Room 1 and can safely walk through the white door. What's the synchronizing word?
This talk will start and end with such puzzles, but will mainly deal with designs in association schemes. The classical motivating example is a collection of kelement subsets of [v] = {1, . . . , v} such that each telement subset of [v] is contained in exactly one of them. A more recent analogue, still closely tied to classical ideas, is the concept of λtransitive sets of permutations. This is based on joint work with Bruce Sagan [J. London Math. Soc., 2006] where we apply a coding theory approach to such collections of permutations using character theory. In the past 11 years, this concept of λtransitive (or λhomogeneous) sets of permutations has been applied by Araújo et al. to the study of synchronizing automata, which is where we started the talk!
 12 October: No seminar
B TERM 2022
 Tuesdays 2:002:50pm, Room SH203, Stratton Hall
 25 October: Bill Martin, WPI, "Ideals of strongly regular graphs and ETFs"
Abstract:
 1 November: Samuel Tripp, WPI, "Grid homology"
Abstract: Knot Floer homology is a powerful suite of knot invariants introduced in the early 2000's. A few years later, this theory was made combinatorial in the form of grid homology, allowing for much greater computational ability. In this talk, we will introduce grid homology, then discuss potential ways to generalize grid homology to the study of tangles.
 8 November: Adam Zsolt Wagner, WPI, "Title TBA"
Abstract:
 15 November: Nathan Uricchio, WPI, "Title TBA"
Abstract:?
 22 November: Oleg Karpenkov, University of Liverpool, "Title TBA"
Abstract:?
 29 November: Speaker?, "Title?"
Abstract:?
 6 December: Neranga Fernando, College of the Holy Cross, "Quandles, racks and shelves"
Abstract: A quandle is a set X with a binary operation ∗ : X × X → X satisfying:The three axioms of a quandle algebraically encode the three Reidemeister moves in knot theory.
 For all x ∈ X, x ∗ x = x
 For all y ∈ X, the map β_{y} : X → X defined by β_{y}(x)= x ∗ y is invertible.
 For all x,y,z ∈ X, (x ∗ y) ∗ z = (x ∗ z) ∗ (y ∗ z).
A rack is a set with a binary operation that satisfies (ii) and (iii), and a shelf is a set with a binary operation satisfying selfdistributivity (iii).
I will begin this talk by giving an introduction to quandles. I will then talk about racks, shelves and quandle rings. Moreover, I will talk about a recent joint work with Matthew Pradeep Goonewardena and Mohamed Elhamdadi on shelves.
 13 December: No seminar?
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.