Discrete Math Seminar Schedule for Fall 2024:

A TERM 2024

• Tuesdays 3:00-3:50pm, Room SH205, Stratton Hall



• 27 August: No seminar
  

• 3 September: Ralihe Raúl Villagrán Olivas, WPI, "The characterization of graphs with two trivial distance ideals"
  Abstract: Distance ideals are algebraic graph invariants that generalize the Smith normal form and the spectrum of distance matrices. The family of graphs with at most two trivial distance ideals (D2) was previously studied and was found to be odd-hole-free, and ℱ-free for a particular set ℱ consisting of 16 graphs with at most 7 vertices. Moreover, a result of Graham and Lovász for the Smith normal form of trees implies that trees are a subset of D2. In this talk, we give a full characterization of D2. In particular, we show that any bipartite graph has at most two trivial distance ideals.

• 10 September: Bill Martin, WPI, "What is a knot? And what is a manifold?"
  Abstract: This tutorial talk will hopefully prepare us for Friday's Conant Lecture in SL104 at 4pm.

• 17 September: Brigitte Servatius, WPI, "Self-dual maps on the sphere"
  Abstract: Given a self-dual map on the sphere, the collection of its self-dual permutations generates a transformation group in which the map automorphism group appears as a subgroup of index two. A careful examination of this pairing yields direct constructions of self-dual maps and provides a classification of self-dual maps. We will explain how to construct an infinite family of strongly involutive polyhedra using doodles and orbifolds.

• 24 September: Doug Stinson, University of Waterloo and Carleton University, "Near-factorizations of groups"
  Abstract: Let (G,.) be a finite multiplicative group with identity e. For A, B ⊆ G, define AB = { gh: g ∈ A, h ∈ B}. We say that (A,B) is a near-factorization of G if |A| × |B| = |G|-1 and G-e =AB. In this talk, we present various existence results for near-factorizations of cyclic and dihedral groups, including techniques for constructing and enumerating nonequivalent near-factorizations. We also discuss connections with other objects of combinatorial interest, including matrix factorizations, partitionable graphs, strong external difference families, and α-valuations (a type of graceful labelling) of graphs.

• 1 October: Colin Defant, Harvard University, "Random combinatorial billiards"
  Abstract: Combinatorial billiards is a new topic that studies rigid and discretized billiard systems that can be modeled combinatorially or algebraically. I will introduce a random combinatorial billiard trajectory depending on some fixed probability p; when p tends to 0, it essentially recovers Thomas Lam's reduced random walk. This random billiard trajectory can also be interpreted as a random growth process on core partitions. The analysis of the random billiard trajectory relies on new finite Markov chains called stoned exclusion processes, which are variants of certain interacting particle systems. These processes have remarkable stationary distributions determined by well-studied polynomials such as ASEP polynomials, inhomogeneous TASEP polynomials, and open boundary ASEP polynomials; in many cases, it was previously not known how to construct Markov chains with these stationary distributions.

• 8 October: Jonathan Shafer, MIT, "Mitigating Undetectable Backdoors in Machine Learning"
  Abstract: As society grows more reliant on machine learning, ensuring the security of machine learning systems against sophisticated attacks becomes a pressing concern. A striking result of Goldwasser et al. (FOCS 2022) shows that an adversary can plant undetectable backdoors in machine learning models, allowing the adversary to covertly control the model's behavior. The backdoors can be planted in such a way that the backdoored machine learning model is computationally indistinguishable from an honest model without backdoors. Goldwasser et al. show undetectability in both black-box and white-box settings.

  In this talk, I'll discuss strategies for defending against undetectable backdoors. The main observation is that, while backdoors may be undetectable, it is possible in some cases to remove the backdoors without needing to detect them. This idea goes back to early works on program self-correcting and random self-reducibility. We show two types of results. First, for binary classification, we show a "global mitigation" technique, which removes all backdoors from a machine learning model under the assumption that the ground-truth labels are close to a decision tree or a Fourier-sparse function. Next, we consider regression where the ground-truth labels are close to a linear or polynomial function in Rⁿ. Here, we show "local mitigation" techniques, which remove backdoors for specific inputs of interest, and are computationally cheaper than global mitigation. All our constructions are black-box. Along the way we prove a simple result for robust mean estimation.

  Joint work with Shafi Goldwasser, Neekon Vafa, and Vinod Vaikuntanathan.

B TERM 2024

• Tuesdays 3:00-3:50pm, Room SH205, Stratton Hall



• 22 October: Sam Adriaensen, WPI, "Recent progress on the union-closed sets conjecture"
  Abstract: The union-closed sets conjecture is an innocent-looking conjecture, that has withstood decades of efforts to prove it. A family F of sets is called union-closed if for any two members of F , their union is also in F . The infamous conjecture states the if F is a union-closed family of finite sets containing a non-empty set, then there must be an element which is contained in at least half of the members of F.

  In this talk, I will not discuss my own research, but instead highlight 2 recent breakthroughs towards proving the conjecture.

  The first one states that it holds for large families. More specifically, Karpas proved in 2017 that if F consists of at least half of the subsets of some finite set, then the conjecture holds. He employed techniques from Boolean analysis.

  The second one, which is even more impressive, occurred about 2 years ago. Gilmer used entropy (in the sense of Shannon) to prove that if F is union-closed, some element occurs in at least 1% of its elements. His arguments were optimized and pushed to about 38% independently by many sets of authors.

  In my opinion, both results use beautiful ideas, which are not that hard to unpack, and are worth taking the time to appreciate.

• 29 October: Bill Martin, WPI, "Cellphones, Euler's Spoilers, and the Four-Color Theorem"
  Abstract: I will talk about a fun connection between cellphone frequency assignment, mutually orthogonal latin squares, and the Four-Color Theorem. This is not my work; the talk is based on the paper "Channel coding strategies for cellular radio" by G.J. Pottie and A.R. Calderbank, IEEE Transactions on Vehicular Technology, a paper cited in 19 patent applications.

• 5 November: No Seminar, WPI Wellness Day
  

• 12 November: No Seminar
  

• 19 November: Vishal Gupta, University of Delaware, "Minimum spectral radius in a given class of graphs"
  Abstract: In 1986, Brualdi and Solheid posed the question of determining the maximum and minimum spectral radius of a graph within a given class of simple graphs. Since then, this problem has been extensively studied for various graph classes. In this talk, I will discuss two such classes: simple connected graphs with a given order and size, and simple connected graphs with a given order and dissociation number. This presentation is based on joint works with Sebastian Cioaba, Dheer Noal Desai, and Celso Marques. (via Zoom)

• 26 November: Sam Adriaensen, WPI, "Association schemes on polynomials over finite fields"
  Abstract: In this talk, we will explore association schemes on polynomials of bounded degree over finite fields, the underlying geometry, and if time permits apply their eigenvalues to give bounds in Erdős-Ko-Rado like intersection problems.

• 3 December: Bill Martin, WPI, "Transitive subsets of finite general linear groups"
  Abstract: In this talk, I will survey the work of Alena Ernst (U. Paderborn) and her thesis advisor Kai-Uwe Schmidt. I will briefly go over the character theory of GL(n,q), the group of all linear transformations from V to itself where V is a vector space of dimension n over a finite field of order q. I will outline Alena's characterization of flag-transitive subsets of GL(n,q) and compare it to what happens in the symmetric group (Sagan & WJM, 2006). As time permits, I'll discuss an interesting Erdos-Ko-Rado result in Alena's thesis.

• 10 December: Speaker TBD, "Title TBA"
  Abstract: TBD

Past Seminars

A,B TERM 2024

• Some day, I'll find the information and perhaps record it here.