# Colloquium Series

## Packing edge colorings of subcubic graphs

### Thursday, April 4, 2024 from 3:00-3:50 pm in BAC 219

**Xujun Liu**, Xi'an Jiaotong-Liverpool University, China

**Title:** Packing edge colorings of subcubic graphs

**Abstract:*** *The notion of packing coloring was inspired by a frequency assignment problem: each broadcast station will be assigned a frequency; stations assigned the same frequency are required to be at least a certain distance apart and each frequency requires a different smallest distance; what is the minimum number of frequencies needed for such an assignment?

A matching (induced matching) is a set of edges E such that each pair of edges in E has distance at least two (three). A (1^j,2^k)-packing edge-coloring of a graph G is a partition of its edge set into j matchings and k induced matchings. Gastineau and Togni showed there are subcubic graphs that are not (1,2,2,2,2,2,2)-packing (abbreviated to (1,2^6)-packing) edge-colorable and not (1^2,2^3)-packing edge-colorable. They also asked the question “whether every subcubic graph is (1,2^7)-packing edge-colorable?”. Very recently, Hocquard, Lajou, and Luzar showed that every subcubic graph is (1,2^8)-packing edge-colorable and (1^2,2^5)-packing edge-colorable. They also conjectured that every subcubic graph is (1,2^7)-packing edge-colorable. Furthermore, Gastineau and Togni, as well as Hocquard, Lajou, and Luzar, have conjectured that every subcubic graph is (1^2,2^4)-packing edge-colorable.

We confirm both conjectures. This is based on a joint work with Santana and Short and a joint work with Gexin Yu.

## 2023-2024 Colloquium Series

* Speaker/Affiliation: *Xingting Wang, Louisiana State University

* Title:* TBA

* Abstract: *TBA

Date/Time/Location:** Thursday, May 9, 2024** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Monroe Eskew, Kurt Gödel Research Center

* Title:* TBA

* Abstract: *TBA

Date/Time/Location:** Thursday, May 2, 2024** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Josh Fitzgerald, Lagrange Labs

* Title:* Zero Knowledge Proofs from Pairings on Elliptic Curves

* Abstract: *TBA

Date/Time/Location:** Thursday, April 25, 2024** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Xujun Liu, Xi'an Jiaotong-Liverpool University, China

* Title:* Packing edge colorings of subcubic graphs

* Abstract:* The notion of packing coloring was inspired by a frequency assignment problem: each broadcast station will be assigned a frequency; stations assigned the same frequency are required to be at least a certain distance apart and each frequency requires a different smallest distance; what is the minimum number of frequencies needed for such an assignment?

A matching (induced matching) is a set of edges E such that each pair of edges in E has distance at least two (three). A (1^j,2^k)-packing edge-coloring of a graph G is a partition of its edge set into j matchings and k induced matchings. Gastineau and Togni showed there are subcubic graphs that are not (1,2,2,2,2,2,2)-packing (abbreviated to (1,2^6)-packing) edge-colorable and not (1^2,2^3)-packing edge-colorable. They also asked the question “whether every subcubic graph is (1,2^7)-packing edge-colorable?”. Very recently, Hocquard, Lajou, and Luzar showed that every subcubic graph is (1,2^8)-packing edge-colorable and (1^2,2^5)-packing edge-colorable. They also conjectured that every subcubic graph is (1,2^7)-packing edge-colorable. Furthermore, Gastineau and Togni, as well as Hocquard, Lajou, and Luzar, have conjectured that every subcubic graph is (1^2,2^4)-packing edge-colorable.

We confirm both conjectures. This is based on a joint work with Santana and Short and a joint work with Gexin Yu.

Date/Time/Location:** Thursday, April 4, 2024** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Matt Menickelly, Argonne National Laboratory

**Title:**~~Stochastic~~ Noisy Black-Box Optimization for Near-Term Quantum Computing

**Abstract:**

While the paradigm of quantum computing has attracted much scientific and popular attention, we must contend with the fact that the current state-of-the-art in quantum hardware is noisy to the point of limited use. A modern and predominant solution for developing and testing quantum algorithms and hardware in the near-term lies in *variational quantum algorithms (VQAs)*. These algorithms effectively separate the inherently quantum aspects of an algorithm from tasks that can be performed efficiently on a classical computer. Almost all VQAs entail casting a problem as one of ground state energy minimization for a problem-defined Hamiltonian. From this perspective, a *classical *optimization algorithm can be implemented on a *classical* computer, treating measurements of the quantum system described by the problem Hamiltonian as a computational black box.

In this talk, I will provide an introduction to VQAs, assuming no prior knowledge about quantum computing. I intend to assume only a healthy familiarity with linear algebra and multivariable calculus (of course, having taken MTH 432/532/632 is a bonus). I will describe my past and ongoing work in the analysis and development of stochastic (actually, noisy) black-box optimization methods which serve as appropriate classical optimizers in most VQAs. I will also start the talk by describing what the national laboratories are and share my perspective on the various roles that applied mathematicians play within them.

Date/Time/Location:** Thursday, March 14, 2024** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Bryan Van Scoy, Miami University, Department of Electrical and Computer Engineering

* Title:* Systematic analysis of iterative black-box optimization algorithms using control theory

* Abstract:* Iterative algorithms are used to solve optimization problems throughout control, robotics, statistics and estimation, signal processing, communication, networks, machine learning, and data science. Recent work from both optimization and control communities has developed a systematic methodology to analyze the worst-case performance of a black-box algorithm over a class of problems. In this talk, we first describe this systematic methodology from a controls perspective and then show how it can be used to analyze and design algorithms in various contexts, such as trading off convergence rate and robustness to gradient noise with noisy first-order oracles, consensus optimization for a multi-agent system, and primal-dual algorithms.

Date/Time/Location:** Thursday, November 16, 2023** from

**3:00-3:50 pm**in

**BAC 219**

** Speaker/Affiliation: **Bob Krueger, University of Illinois, Urbana-Champaign

* Title: *Sparse random analogues of classical combinatorial theorems

* Abstract:* A successful trend in modern extremal/probabilistic combinatorics is the investigation of how well classical theorems, like those of Ramsey, Turán, and Szemerédi, hold in sparse random contexts. Graph and hypergraph container methods have played a big role in improving our knowledge of these sparse structures. I will present an overview of this area, including some joint work with Jozsef Balogh and Haoran Luo on a random version of the Erdős-Ko-Rado Theorem and Sperner's Theorem. If time permits, I will also talk about some recent work on the typical behavior of graph homomorphisms from expanders, including Lipschitz functions on expanders.

Date/Time/Location:** Thursday, November 9, 2023** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Todd Kapitula, Calvin University

* Title: *Viewing spectral problems through the lens of the Krein matrix

* Abstract:* Determining the stability of nonlinear waves usually requires that the spectrum for the appropriate linearized operator be known. In the case of Hamiltonian systems, the spectrum has a great deal of structure. This structure can be exploited to determine things like the number of (potentially) unstable eigenvalues, or when a destabilizing Hamiltonian-Hopf bifurcation can occur. In my talk I will discuss some of the mathematical tools which allow us to address these questions. Applications will also be given.

Date/Time/Location:** Thursday, September 28, 2023** from

**3:00-3:50 pm**in

**BAC 219**

* Speaker/Affiliation: *Khodakhast Bibak, Miami University, Department of Computer Science and Software Engineering

* Title:* Authentication of variable length messages in quantum key distribution using number-theoretic and combinatorial techniques

* Abstract:* Authentication plays a critical role in the security of quantum key distribution (QKD) protocols. We propose using Polynomial Hash and its variants for authentication of variable length messages in QKD protocols. Since universal hashing is used not only for authentication in QKD but also in other steps in QKD like error correction and privacy amplification, and also in several other areas of quantum cryptography, Polynomial Hash and its variants as the most efficient universal hash function families can be used in these important steps and areas, as well. We introduce and analyze several efficient variants of Polynomial Hash and, using deep results from number theory, prove that each variant gives an $\varepsilon$-almost-\(\Delta\)-

Date/Time/Location:** Thursday, September 14, 2023** from

**3:00-3:50 pm**in

**BAC 219**