The RIT Discrete and Computational Mathematics Seminar

Overview

Welcome to the Discrete and Computational Mathematics Seminar at RIT (DisCoMathS)! We are a big tent seminar series for everything discrete: graph theory, combinatorics, combinatorial optimization, applications of discrete mathematics, and computational aspects of all these subjects. During the Fall 2021 semester the seminar meets weekly (see the schedule below for the exact dates) in Thomas Gosnell Hall (GOS-2305) and online via Zoom. All talks are scheduled from 2:30PM until 3:30PM Rochester time on Fridays (unless otherwise noted). For seminar announcements, schedule updates, and Zoom links to the seminars, be sure to subscribe to the mailing list (see below).

DisCoMathS is open to the public, and everyone is welcome to attend.

The seminar is organized this semester by Brendan Rooney. If you would like to give a seminar, please contact discomaths@rit.edu.

Mailing List

Seminar announcements and Zoom links will be sent via the DisCoMathS mailing list. Join now!

Upcoming Seminar

September 17

2:30-3:30PM in GOS-2305

Speaker: Shahla Nasserasr
Title: Rigid Linkages and Eigenvalues

Abstract: Given an assignment of colours blue and white to the vertices of graph $G$, the zero forcing rule determines a subset of white vertices to be re-coloured blue. The zero forcing process applies this rule in discrete time-steps until no more changes are possible. Rigid linkage forcing is defined similarly to the standard zero forcing process. Rigid linkages are used to provide more information on the multiplicities of the eigenvalues, and the relationship between the eigenvalues of matrices related to graphs.

In this talk, some properties and applications of the rigid linkage forcing process will be discussed.

Future Seminars

September 24

Speaker: Brendan Rooney
Title: Combinatorial Orthogonality and Graphs with $q=2$

Abstract: Two vectors are combinatorially orthogonal if the size of the intersection of their supports is not 1. An $n\times 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 in $\mathcal{S}(G)$ (the set of symmetric matrices with the same off-diagonal zero-pattern as the adjacency matrix of $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 finding $q(G)$, and characterizing graphs with $q=2$.


October 1

Speaker: Bonnie Jacob
Title: Failed Zero Forcing and the Zero Forcing Span of a Graph

Abstract: TBA


October 8

Speaker: Kristijan Tabak (RIT Croatia)
Title: Binary Fano Plane Automorphism of Order 7 - Finally Resolved

Abstract: TBA


October 15

Speaker: Peter Maceli (Ithaca College)
Title: Chi-boundedness

Abstract: If a graph has bounded clique number, and sufficiently large chromatic number, what can we say about its induced subgraphs? In the early 1980's András Gyárfás made a number of challenging conjectures about this. In this talk, we will give a brief survey of how these questions seek to generalize the class of perfect graphs, along with some recent results.


October 22

Speaker: Kristijan Tabak (RIT Croatia)
Title: On $p$-Groups with Minimal Subgroup Centralizers - New Results

Abstract: TBA


October 29

Speaker: Adam Giammarese
Title: A Parameter-Free Approach to Forecasting Chaotic Time Series

Abstract: TBA


November 5

Speaker: Quinn Kolt
Title: Constructing Unitary Fusion Category Representations with the Jellyfish Algorithm

Abstract: The graphical calculus is a modern technique for classifying and constructing “unitary fusion” categories, categories which model elementary particles that merge and split. In particular, if one can obtain enough diagrammatic relations to evaluate all “closed” diagrams, this graphical calculus uniquely describes the category. However, in order to prove existence, one must also find a representation of the category. Cuntz algebras, a type of C*-algebra, are a natural home for the representations of many fusion categories. The Jellyfish algorithm allows us to use diagrams to find what these Cuntz algebra representations should be in an intuitive way. Using this computation, we can then prove existence by showing that this construction is indeed a well-defined representation in the associated Cuntz algebra. In this talk, I will apply this process on the unitary fusion category with Fibonacci fusion rules.


November 12

Speaker: Yutong Wu
Title: Failed Positive Semidefinite Zero Forcing

Abstract: TBA


November 19

Speaker: Matt Coppenbarger
Title: An Impartial Combinatorial Game on a $3\times 3$ Board with Magic Square Constraints

Abstract: TBA


December 3

Speaker: TBA
Title: TBA

Abstract: TBA

Past Seminars

This is still the future!

February 15

Speaker: Brendan Rooney
Title: The Colin de Verdière Number of a Graph.

Abstract: This talk is the first in a series of two talks on "strong" matrix conditions. In this talk we define the Colin de Verdière graph invariant, and show that it is a minor monotone parameter.

The Colin de Verdière number of graph $G$ is the maximum multiplicity of $0$ as an eigenvalue over matrices compatible with the adjacency matrix of $G$. In order for $M$ to be compatible with $G$ it must (among other things) satisfy the Strong Arnold Hypothesis. Our focus will be on this property, how it can be interpreted, and how it is applied. We will also discuss the characterization of planar graphs by their Colin de Verdière number. Our discussion follows van der Holst, Lovász, and Schrijver (The Colin de Verdière graph parameter, 1997).


February 22

Speaker: Brendan Rooney
Title: The Strong Spectral Property and the Strong Multiplicity Property.

Abstract: This talk is the second in a series of two talks on "strong" matrix conditions. In this talk we focus on two analogous properties to the Strong Arnold Property, and their connection to the minimum number of distinct eigenvalues of a graph.

For a graph $G$ on $n$ vertices, $\mathcal{S}(G)$ is the space of $n\times n$ symmetric matrices whose off-diagonal zero pattern exactly matches that of $A(G)$. We are interested in finding $q(G)$, the minimum number of distinct eigenvalues of a matrix $M\in\mathcal{S}(G)$. A matrix $M$ has the Strong Spectral Property (SSP) if a pair of manifolds associated with $M$ intersect transversally at $M$. We will unpick what this means, and see how it can be used to give a lower bound of $q(G)$. Our discussion follows two papers of Barrett et al., "Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph" (2016), and "The inverse eigenvalue problem of a graph: Multiplicities and minors" (2017).


March 1

Speaker: Shahla Nasserasr
Title: A Nordhaus-Gaddum conjecture on the eigenvalues of graphs and their structures.

Abstract: For a graph $G$ on $n$ vertices, and a parameter $p$ related to $G$, a Nordhaus-Gaddum type problem is to find an upper bound and a lower bound as functions of $n$ for $p(G)+p(\overline{G})$. When $p(G)=q(G)$, the minimum number of distinct eigenvalues of $G$ (introduced in the previous talk by Dr. Rooney), it is conjectured that the upper bound is $n+2$. The conjecture is proved for many families of graphs. In this talk, we will focus on this conjecture and the families of graphs for which the conjecture is true. The talk will be out of the paper https://www.sciencedirect.com/science/article/pii/S0024379518305561


March 8

Speaker: Shahla Nasserasr
Title: Orthogonal matrices with a given pattern of zero entries.

Abstract: For a given graph $G$, let $S(G)$ be the set of all symmetric matrices such that the $(i,j)$ entry with $i\neq j$ is zero exactly when $ij$ is not an edge of $G$. The case when $S(G)$ contains an orthogonal matrix is especially interesting because that means $G$ has two distinct eigenvalues ($q(G)=2$). It is known that for any two connected graphs with the same number of vertices there is a symmetric orthogonal matrix compatible with their join. This statement is generalized by Levene et al. to graphs that are not necessarily connected. In this talk, we will focus on this generalization in the paper: https://arxiv.org/abs/2012.12694


March 15

Speaker: Darren Narayan
Title: Orthogonal matrices with zero diagonal.

Abstract: A presentation will be given on the paper "On orthogonal matrices with zero diagonal" by R. Bailey and R. Craigen. In this paper the authors consider real orthogonal $n\times n$ matrices whose diagonal entries are zero and off-diagonal entries nonzero. They use these results to determine the minimum number of distinct eigenvalues of matrices associated with some families of graphs, and consider the related notion of orthogonal matrices with a partially-zero diagonal.


March 29

Speaker: Bonnie Jacob
Title: Relating linkages to the inverse eigenvalue problem on a graph.

Abstract: In this talk, we will describe the results presented in Rigid linkages and partial zero forcing by Ferrero et al. (2019). We will discuss linkages and rigid linkage forcing. We will also explore  how these concepts relate to matrix eigenvalue multiplicities. 


April 5

Speaker: Louis Deaett (Quinnipiac University)
Title: Matroids and the minimum rank problem for matrices.

Abstract: Suppose the only information we have about a matrix is its number of rows, its number of columns, and whether each entry is zero or nonzero.  What can this tell us about the rank of the matrix?  This is a well-studied question in combinatorial matrix theory.  In this talk, we discuss how to place this problem within the context of matroid theory, which can be thought of as a purely combinatorial abstraction of the way linear independence and rank behave over a vector space.  We will revisit some known results and show how they can be better understood in terms of matroids.  We will also use the connection to matroid theory to explain and improve on some existing examples, obtain a couple of new results, and highlight some new research questions opened up by this connection.


April 12

Speaker: Victoria McGraw
Title: Spanning Shallow-Light Trees.

Abstract: Shallow-Light Trees are a form of bicriteria optimization combining minimum weight spanning trees and shortest path graphs. Spanning Shallow-Light Trees are the simplest form of this optimization. However, the extensions and variations of Shallow-Light Trees are often applied to network optimization areas such as buy-at-bulk, routing topology, and data allocation problems. This presentation will provide an introduction and overview of the applications and construction of Spanning Shallow-Light Trees.


April 19

Speaker: Jobby Jacob
Title: Graphs with two distinct eigenvalues.

Abstract: We will discuss some of the results from the paper by Chen, Grimm, McMichael and Johnson, Undirected graphs of Hermitian matrices that admit only two distinct eigenvalues. In particular, we will discuss construction techniques used in this paper to study graphs where one of the two eigenvalues has multiplicity two.


April 26

Speaker: Noah Collins
Title: Extremal Graph Theory and Spectral Radii.

Abstract: One area of extremal graph theory involves looking at graphs being embedded in certain surfaces. From the paper Three Conjectures In Extremal Spectral Graph Theory, the authors show the structure of planer and outerplanar graphs when embedded in the plane. In particular, the authors look at the spectral radii of outerplanar and planer graphs. By looking at these graphs' spectral radii and maximizing the authors are able to deduce the structure of outerplanar and planar graphs when embedded in the plane. 

September 18

Speaker: Stanisław Radziszowski
Title: Chromatic Vertex Folkman Numbers

Abstract: For graph $G$ and integers $a_1 \ge \cdots \ge a_r \ge 2$, we write $G \rightarrow (a_1 ,\cdots ,a_r)^v$ if and only if for every $r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i \in \{1, \cdots, r\}$. The vertex Folkman number $F_v(a_1 ,\cdots ,a_r; s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G \rightarrow (a_1 ,\cdots ,a_r)^v$. It is well known that if $G \rightarrow (a_1 ,\cdots ,a_r)^v$ then $\chi(G) \geq m$, where $m = 1+ \sum_{i=1}^r (a_i - 1)$. In this paper we study such Folkman graphs $G$ with chromatic number $\chi(G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s \ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G \rightarrow (s,\cdots_r,s)^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ with respect to this property. Among others we conjecture that for every $s \ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s;s+1)$ vertices with $\chi(G)=2s-1$ and $G\rightarrow (s,s)^v$.

The paper and slides for this talk are available at #1 here.


September 25

Speaker: Brendan Rooney
Title: Efficient Domination in Regular Graphs

Abstract: A function $f:V(G)\rightarrow\{0,\ldots,j\}$ is an efficient $(j,k)$-dominating function on $G$ if $\sum_{u\in N[v]}f(u)=k$ for all $v\in V(G)$ (here $N[v]=N(v)\cup\{v\}$ is the closed neighbourhood of $v$). Efficient $(j,k)$-domination was introduced by Rubalcaba and Slater (2007) as a generalization of perfect domination, and efficient $k$-domination. We look at efficient domination on regular graphs, applying some standard tools from linear algebra and algebraic graph theory. Using these ideas we give a partial characterization of the values $k$ for which the Hamming graphs $H(q,d)$ are efficiently $(1,k)$-dominatable. This extends the theorem of Tietavainen-van Lint-Leont’ev-Zinov’ev characterizing codes that meet the sphere packing bound.


October 2

Speaker: Bonnie Jacob
Title: Minimum Zero-Diagonal Rank and Failed Skew Zero Forcing of Graphs

Abstract: Associated with any simple graph $G$ is a family of symmetric zero-diagonal matrices with the same zero-nonzero pattern as the adjacency matrix of $G$.  There is a strong connection between the ranks of these matrices and the generalized cycles that exist as subgraphs of $G$. In this talk, we characterize all connected graphs $G$ with minimum rank of $3$ or below, as well as all connected graphs with minimum rank of $n$, the order of the graph.   It turns out that  the minimum rank is the order of the graph if  and  only  if $G$ has  a  unique  spanning  generalized  cycle,  also  known  as  a  unique perfect $[1,2]$-factor, among other names.  We present an algorithm for determining whether a graph has a unique spanning generalized cycle.  We also determine the maximum zero-diagonal rank of a graph, which is also related to generalized cycles, and then show that there exist graphs $G$ for which some ranks between minimum rank and the maximum rank of $G$ cannot be realized.

Related to the notion of minimum rank is the idea of zero forcing.  For minimum zero-diagonal rank, the skew zero forcing number and failed skew zero forcing number provide bounds on the rank of a graph.  We present some results for the failed skew zero forcing number of a graph.  

These results are based on joint work with C. Grood, L. Hogben, J. Harmse, T. J. Hunter, A. Klimas, S. McCathern, T. Ansill, J. Penzellna, and D. Saavedra.  Paper.


October 9

Speaker: Darren Narayan
Title: Symmetry in Point-Block Incidence Graphs

Abstract: We present infinite families of graphs $G$ where all symmetries can be removed by fixing a single vertex. That is, mapping any vertex to itself results in the trivial automorphism. These graphs, called point-block incidence graphs, lie at the intersection of graph theory and combinatorial design theory. A point-block incidence graph is a bipartite graph $G=(P,B)$ with a set of point vertices $P=\{p_{1},p_{2},...,p_{r}\}$ and a set of blocks $B=\{B_{1},B_{2},...,B_{s}\}$ where $p_{i}\in P$ is adjacent to $B_{j}\in B\Leftrightarrow p_{i}\in B$. A vertex $v$ in a graph $G$ is fixed if it is mapped to itself under every automorphism of $G$. The fixing number of a graph $G$ is the minimum number of vertices, when fixed, fixes all of the vertices in $G$ and was introduced by Laison, Gibbons, Erwin, and Harary.


We present infinite families of graphs with a fixing number of $1$, and further fixing any vertex fixes every vertex of the graph. We also show that other point-block incidence graphs can have a high degree of symmetry and a large fixing number as they can be expressed as the disjoint union of copies of $P_{2}\times P_{n}$, $K_{3,3}$, or Möbius ladder graphs. This is joint work with Josephine Brooks, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, and Brendan Rooney.


October 16

Speaker: Kristijan Tabak (RIT Croatia)
Title: An Algebraic Proof That the Binary Fano Plane is Almost Rigid

Abstract: The existence of a binary $q$-analog of a Fano plane is still unknown. Kiermaier, Kurz and Wassermann proved that automorphism group of a binary $q$-analog of a Fano plane is almost trivial, it contains at most two elements. The method used there involved Kramer - Masner method together with an extensive computer search. In this paper we provide an algebraic (computer free) proof that automorphism group of a binary $q$-analog of a Fano plane contains at most two elements. We used group theory with calculations in a suitable group rings.


October 23

Speaker: Daniela Elizondo and Henry Fleischmann
Title: Efficient $(j,k)$-Domination on Chess Graphs

Abstract: Graphs defined by the legal moves of a chess piece are a classical setting for efficient domination. For a graph $G$, a function $f: V(G) \rightarrow \{0, 1, \ldots, j \}$ is an efficient $(j,k)$-dominating function if, for all $v \in V(G)$, $\sum_{w \in N[v]} f(w) = k$, where $N[v]$ is the closed neighborhood of $v$ (introduced by Rubalcaba and Slater, 2007).
    
We completely characterize efficient $(j,k)$-domination on King's graphs. This result generalizes to a construction that shows $G\boxtimes H$ is efficiently $(j,k)$-dominatable if and only if both $G$ and $H$ are. Additionally, we describe several necessary conditions for efficient $(j,k)$-domination, following our observations on Bishop's graphs.
    
On the torus, the Queen's and Bishop's graphs are realizable as Cayley graphs. We apply character theory to calculate the spectra of these graphs, through which we determine their efficient $(j,k)$-dominating functions.
    
For the standard $n\times n$ Queen's graph, we exploit an equitable partition to show computationally that, for $4 \leq n \leq 571$, efficient $(j,k)$-domination occurs only when $n = 10$. Expanding this approach, we construct an infinite class of graphs with an efficient $(j,k)$-dominating function from analogous equitable partitions.


October 30

Speaker: Shahla Nasserasr
Title: Achievable Multiplicity Partitions of a Graph

Abstract: For a graph $G$, the class of real-valued symmetric matrices whose zero-nonzero pattern of off-diagonal entries is described by the adjacencies in $G$ is denoted by $S(G)$. The inverse eigenvalue problem for the multiplicities of the eigenvalues of $G$ is to determine for which ordered list of positive integers $m_1\geq m_2\geq \cdots\geq m_k$ with $\sum_{i=1}^{k} m_i=|V(G)|$, there exists a matrix in $S(G)$ with distinct eigenvalues ${\lambda_1,\lambda_2,\cdots, \lambda_k}$ such that $\lambda_i$ has multiplicity $m_i$. A related parameter is $q(G)$, the minimum number of distinct eigenvalues of a matrix in $S(G)$. We study graphs that can achieve two distinct eigenvalues ($q(G)=2$) with given multiplicities. This is joint work with the Discrete Mathematics Research Group of Regina.


November 6

Speaker: Nate Cahill
Title: Relaxing Balanced Graph Cuts Part 2

Abstract: In April, I showed how image segmentation can be thought of as a process of partitioning an image into a small number of subsets, and how image segmentation algorithms can often be modelled as graph partitioning problems which are typically NP-hard. In this talk, we’ll focus on a particular instance of this algorithm, called “Balanced Cuts,” by describing the cost function whose minimum coincides with the optimal partitioning, and by showing how a relaxation of the discrete minimization problem yields a continuous problem that can be solved through a generalization of iteratively reweighted least squares (IRLS).


November 13

Speaker: John Whelan
Title: Mismatch Metrics, Lattice Coverings and Coordinate Choices: Adventures in the Parameter Space of Continuous Gravitational Waves

Abstract: We describe the application of the lattice covering problem to the placement of templates in a search for continuous gravitational waves from the low-mass X-Ray binary Scorpius X-1.

Sco X-1 is a neutron star in a binary system with a low-mass companion star.  It is believed to be rapidly spinning and a promising source of continuous gravitational waves.  The signal received by an observatory such as LIGO, Virgo or KAGRA depends on the parameters of the system, and a search for that signal loses sensitivity if the incorrect values are used for those parameters.  Several of the parameters (rotational frequency, projected orbital radius, orbital period and orbital phase) are uncertain, and one method to ensure that the signal is not missed is to perform the search at each point in a lattice covering the relevant parameter space.

The loss of signal-to-noise ratio (SNR) associated with an incorrect choice of parameters is, in a generic Taylor expansion, a quadratic function of the parameter offsets.  This allows us to write the fractional loss in SNR, also known as the mismatch, as a distance using a metric on parameter space.  In general, this metric will vary over the parameter space (i.e., the associated geometry will have intrinsic curvature), but we can divide the parameter space into small enough pieces that the space is approximately flat, and the metric can be assumed to be constant.  In that case, there exists a transformation to Euclidean coordinates.  The problem of placing templates so that the mismatch of any point in parameter space from the nearest template is no more than some maximum mismatch $\mu$ is then equivalent to the problem of covering the corresponding Euclidean space with spheres of radius $\mu$.  The most efficient covering lattice in $n\le 5$ dimensions is the family $A_n^*$, which includes the hexagonal lattice $A_2^*$ and the body-centered cubic lattice $A_3^*$.  For example, the density of lattice points for $A_4^*$ is a factor of $2.8$ lower than the corresponding hypercubic ($\mathbb{Z}^4$) lattice.

We use the LatticeTiling module in the LIGO Algorithms Library (lalsuite) to investigate efficient lattice coverings for the parameter space of a search for Sco X-1 using advanced LIGO data.  We show how the search can be made more efficient by 1) replacing a hypercubic grid with an $A_n^*$ lattice, 2) accounting for the elliptical boundaries associated with the correlated prior uncertainties between orbital period and orbital phase, and 3) defining a "shearing" coordinate change such that a particular combination of the orbital period and orbital phase is "unresolved", and explicitly searching only in the other three dimensions of the parameter space.  These improvements allow the search to be carried out using fewer computational resources.  Alternatively, since the search method we use is "tunable", with a tradeoff between
computational cost and sensitivity, the more efficient lattice allows a more sensitive search to be done at the same computing cost.

This work is a collaboration between AST PhD student Katelyn Wagner and myself, with help from AST PhD student Jared Wofford.


November 20

Speaker: Rigoberto Florez
Title: Some Enumerations on Non-decreasing Dyck Paths

Abstract: A Dyck path is a lattice path in the first quadrant of the $xy$-plane that starts at the origin and ends on the $x$-axis. It consists of the same number of North-East ($U$) and South-East ($D$) steps. A pyramid is a subpath of the form $U^nD^n$. A valley is a subpath of the form $DU$. The height of a valley is the $y$-coordinate of its lowest point. A Dyck path is called non-decreasing if the heights of its valleys form a non-decreasing sequence from left to right.

In this talk, we count several aspects of non-decreasing Dyck paths. We count, for example, the number and weight of pyramids and numbers of primitive paths. In the end of the talk we introduce the concept of symmetric pyramids and count them. Throughout the talk, we give  connections (bijective relations) between non-decreasing Dyck paths  with other objects of the combinatorics. Some examples are, words, trees, polyominoes. This is a joint work with Eva Czabarka, José L. Ramírez, and Leandro Junes.

February 12

Speaker: Brendan Rooney
Title: An Introduction to Cayley Graphs

Abstract: Cayley graphs are graphs constructed from groups. We show how questions about graph symmetry naturally lead to Cayley graphs. We also survey some classical results about Cayley graphs.


February 19

Speaker: Brendan Rooney
Title: More Cayley Graphs

Abstract: We continue our discussion of Cayley graphs, shifting our focus to structural questions. We will look at cliques, neighborhoods, colorings, and more!


February 26

Speaker: Bonnie Jacob
Title: Construction of Graphs That Swap Distance-One and Distance-Two Pairs of Vertices

Abstract: The distance $d_G(u,v)$ between vertices $u$ and $v$ in a graph $G$ with vertex set $V(G)$ is the number of edges on a shortest path from $u$ to $v$.  From a graph $G$, suppose we want to construct a new graph $H$ that has the same vertex set of $G$, but $d_{H}(u,v) = 1$ if and only if $d_G(u,v)=2$, and $d_{H}(u,v) = 2$ if and only if $d_G(u,v)=1$.  For most choices of $G$, we would be out of luck.  However, if $G=C_5$, for example, we can find such a graph $H$.  In fact, $H=G=C_5$.  

In this talk, we will discuss the motivation for considering this property and the conditions under which it holds.  


March 18

Speaker: Brendan Rooney
Title: Hardness of Finding Maximum Cliques in Cayley Graphs

Abstract: Computing the clique number of a general graph is well-known to be NP-Hard. Codenotti et al. [Bruno Codenotti, Ivan Gerace, and Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra Appl., 285(1-3): 123--142, 1998] showed that computing clique number and chromatic number are still NP-Hard problems for the class of circulant graphs. This result demonstrates that the assumption of vertex transitivity does not make computing clique numbers or chromatic numbers easier. It also raises the question of whether there are classes of Cayley graphs for which these problems are easy to solve.

We outline proof that computing clique number is NP-Hard for the class of Cayley graphs for the groups $G^n$, where $G$ is any fixed finite group. In particular, this shows that these problems are NP-Hard for cubelike graphs. Our method brings together: a construction for embedding graphs in Cayley graphs; quotients of groups; quotients of graphs; and, Goppa codes.


March 25

Speaker: Nishant Malik
Title: Networks based analysis of regional and global climate systems

Abstract: Analysis of large-scale spatiotemporal datasets of various regional and global climate phenomena is a challenging task, a recently developed innovative way to analyze these datasets is employing methods of network science.  These methods are especially useful in situations where the underlying motivation for the analysis is identifying connectivity patterns between various dynamical features of the climate system.  For example, using these methods, we can answer questions such as the role of ENSO (El Niño–Southern Oscillation) in global rainfall patterns.  

In this talk, I will illustrate the effectiveness of network science-based climate data analysis by applying it to rainfall patterns over South Asia and East Asia. For monsoon over South Asia, I will show that we can identify various spatial patterns that precede extreme rainfall,  these patterns can not only be used as early warning signs for extreme rainfall events but can also provide insights into various dynamical features of monsoon. Furthermore, for the East Asian region, using the community detection algorithm, we delineate regions of coherent rainfall during different seasons. Time permitting, I will show some of our recent work on predicting monsoon and ENSO using network analysis. 


April 1

Speaker: Manuel Lopez
Title: Finding polynomials for functions modulo a prime with a little help from linear algebra

Abstract: Every function $f:\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$, where $p$ is a prime, can be expressed as a polynomial. There wasn't any easily computable approach I could find, so I worked out one approach. I will also motivate why such a computational tool is useful for number-theoretic purposes.


April 8

Speaker: Darren Nararyan
Title: Graph theory metrics for analyzing functional MRI data and brain connectivity

Abstract:  In recent years metrics from the theory of graphs and networks have emerged as powerful means for analyzing functional MRI data. These include an array of properties found commonly applied to the realm of transportation and social networks, such as the characteristic (average) path length, the clustering coefficient, as well as global and local efficiency. We have also focused on the concept of betweenness centrality, which measures the frequency in which shortest paths between regions pass through a particular region or connection. The talk will include an overview of these methods and show how they can be applied to analyze brain connectivity.


April 15

Speaker: Matthew Coppenbarger
Title: An Introduction to Combinatorial Game Theory

Abstract: Combinatorial Game Theory is based on a simple and intuitive recursive definition of games, which yields a very rich algebraic structure:  games can be added and subtracted in a very natural way, forming an abelian group with a partial ordering.  The talk will also introduce some of the fundamental games that motivate the theory.


April 22

Speaker: Nathan Cahill
Title: Relaxing Balanced Graph Cuts

Abstract: In the computer vision community, a huge focus of research over the last generation has been on analyzing and understanding images. One common “low-level” image analysis task, image segmentation, aims to partition an image into a small number of subsets that can be input into subsequent high-level image understanding tasks. In this talk, we’ll explore how image segmentation algorithms can often be modeled as graph partitioning problems which are typically NP-hard, and then we’ll discuss how some of these problems can be relaxed to generate heuristics that can be solved rapidly.


April 29

Speaker: Stanislaw Radziszowski
Title: Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs

Abstract: We study the Shannon capacity of channels in the context of Ramsey numbers. We overview some of the results on channel capacity, and how Ramsey-type constructions may enhance them. A new lower bound for a special type of multicolor Ramsey numbers is presented, which implies that the supremum of the Shannon capacity over all graphs with independence 2 cannot be achieved by any finite graph power. This generalizes to graphs with any bounded independence number.

The paper and slides are available at #33 here.

September 25

Speaker: Brendan Rooney
Title: Hedetniemi's Conjecture: Past, Present, and Future

Abstract: In 1966 Stephen Hedetniemi conjectured that the chromatic number of the direct product of graphs $G$ and $H$ is equal to the minimum of the chromatic numbers of $G$ and $H$. In the 53 years it has stood open, this conjecture has inspired a great deal of research on graph colourings and homomorphisms. Very recently (May of 2019!), Yaroslav Shitov published a construction on the arXiv giving counterexamples to Hedetniemi's Conjecture. I will give an introduction to this conjecture, some evidence for its validity, an account of Shitov's construction, and some results that suggest further directions for research.


October 9

Speaker: Stanisław Radziszowski
Title: On a Diagonal Conjecture for Classical Ramsey Numbers

Abstract: Let $R(k_1,\ldots,k_r)$ denote the classical $r$-color Ramsey number for integers $k_i\geq 2$. The Diagonal Conjecture (DC) for classical Ramsey numbers poses that if $k_1,\ldots,k_r$ are integers no smaller than $3$ and $k_{r-1}\leq k_r$, then $R(k_1,\ldots,k_{r-2},k_{r-1}-1,k_r+1)\leq R(k_1,\ldots,k_r)$. We obtain some implications of this conjecture, present evidence for its validity, and discuss related problems.

Let $R_r(k)$ stand for the $r$-color Ramsey number $R(k,\ldots,k)$. It is known that $\lim_{r\rightarrow\infty}R_r(3)^{1/r}$ exists, either finite or infinite, the latter conjectured by Erdős. This limit is related to the Shannon capacity of complements of $K_3$-free graphs. We prove that if (DC) holds, and $\lim_{r\rightarrow\infty}R_r(3)^{1/r}$ is finite, then $\lim_{r\rightarrow\infty}R_r(k)^{1/r}$ is finite for every integer $k\geq 3$.

Paper: arxiv.org/abs/1810.11386.
Slides: ram19a.pdf.


October 23

Speaker: Bonnie Jacob
Title: Results and Remaining Questions About Failed Zero Forcing on Directed Graphs

Abstract: Let $D$ be a simple digraph (directed graph) with vertex set $V(D)$ and arc set $A(D)$ where $n=|V(D)|$, and each arc is an ordered pair of distinct vertices. If $(v,u) \in A(D)$, then $u$ is considered an out-neighbor of $v$ in $D$. Initially, we designate each vertex to be either filled or empty. Then, the following color change rule (CCR) is applied: if a filled vertex $v$ has exactly one empty out-neighbor $u$, then $u$ will be filled. The process continues until either all of the vertices in $V(D)$ are filled, or the CCR restricts the remaining empty vertices from being filled. If all vertices in $V(D)$ are eventually filled, then the initial set is called a zero forcing set (ZFS); if not, it is a failed zero forcing set (FZFS).

In this talk, we define the failed zero forcing number $\operatorname{F}(D)$ on a digraph, which is the maximum cardinality of any FZFS. The zero forcing number, $\operatorname{Z}(D)$, is the minimum cardinality of any ZFS. We characterize oriented graphs that have $\operatorname{F}(D)<\operatorname{Z}(D)$ and present a list of digraphs with the same property. We also characterize digraphs with high and low values of $\operatorname{F}(D)$. We also discuss some open questions that remain about failed zero forcing on directed graphs.

This is based partially on work during the 2018 REU together with Alyssa Adams of Youngstown State University.


November 6

Speaker: Darren Narayan
Title: The Asymmetric Index of a Graph

Abstract: A graph $G$ is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erdős and Rényi (1963). They suggested the problem of starting with an asymmetric graph and removing some number $r$ of edges and/or adding some number $s$ of edges so that the resulting graph is non-asymmetric. Erdős and Rényi defined the degree of asymmetry of a graph to be the minimum value of $r+s$. In this paper, we define another property that measures how close a given non-asymmetric graph is to being asymmetric. We define the asymmetric index of a graph $G$, denoted $ai(G)$, to be the minimum of $r+s$ so that the resulting graph $G$ is asymmetric.

We investigate the asymmetric index of both connected and disconnected graphs. We prove that for any non-negative integer $k$, there exists a graph $G$ where $ai(G)=k$. We show that the asymmetric index of a cycle with at least six vertices is two, and provide a complete characterization of all possible pairs of edges that can be added to a cycle to create an asymmetric graph. In addition we determine the asymmetric index of paths, certain circulant graphs, Cartesian products involving paths and cycles, and bounds for complete graphs, and complete bipartite graphs.


November 20

Speaker: Jobby Jacob
Title: On the Characterization of Graphs Based on Their Rank Numbers

Abstract: For a graph $G$, an onto function $f$ from the vertex set of $G$ to $\{1,2,\ldots,k\}$ is a $k$-ranking if $f(u)=f(v)$ implies that every $uv$-path contains a vertex $x$ such that $f(x)>f(u)=f(v)$. The rank number of a graph $G$ is the minimum value of $k$ such that $G$ has a $k$-ranking.

We will discuss the rankings of some classes of graphs, and in particular, we will discuss a recent result on characterizing graphs with large rank numbers.


December 4

Speaker: Matthew Coppenbarger
Title: Iterations of the Sisyphus Function

Abstract: The Sisyphus function is defined; and we determine the smallest non-negative integer $n$ requiring a specified number of iterations of the function that must be applied to $n$ until the sequence generated by the iterations of this function becomes stable or cycles.