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 Spring 2021 semester the seminar meets weekly (see the schedule below for the exact dates) online via Zoom. All talks are scheduled from 2:00PM until 3:00PM Rochester time on Mondays (with the exception of one talk per month that will run 2:15PM-3:15PM to accommodate staff meetings). 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

February 15

2:15PM-3:15PM on Zoom

Speaker: Brendan Rooney
Title: TBA

Abstract: TBA

Future Seminars

February 22

Speaker: Brendan Rooney
Title: TBA

Abstract: TBA


March 1

Speaker: Shahla Nasserasr
Title: TBA

Abstract: TBA


March 8

Speaker: Shahla Nasserasr
Title: TBA

Abstract: TBA


March 15

Speaker: Darren Narayan
Title: TBA

Abstract: TBA


March 22

Speaker: Bonnie Jacob
Title: TBA

Abstract: TBA


March 29

Speaker: Jobby Jacob
Title: TBA

Abstract: TBA


April 5

Speaker: TBA
Title: TBA

Abstract: TBA


April 12

Speaker: TBA
Title: TBA

Abstract: TBA


April 19

Speaker: TBA
Title: TBA

Abstract: TBA


April 26

Speaker: TBA
Title: TBA

Abstract: TBA

Past Seminars

This is still the future!

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, neighbourhoods, colourings, 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 motivation for considering this property and 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 number or chromatic number easier. It also raises the question of whether there are classes of Cayley graphs for which these problems are easy to solve.

We outline a 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 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 motivates 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 into 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 modelled as graph partitioning problems which are typically NP-hard, and then we’ll discuss how the 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 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.