Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2019

June 7 P. Morris, Freie Universitaet Berlin Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu
Abstract:    A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together cover all the vertices in $G$. In this paper we consider perfect $K_r$-tilings in the setting of randomly perturbed graphs; a model introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it. Specifically, given any fixed $0< \alpha <1-1/r$ we determine how many random edges one must add to an $n$-vertex graph $G$ of minimum degree $\delta (G) \geq \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$-tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumps' at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $\alpha =0$) and that of Hajnal and Szemer\'edi (which demonstrates that for $\alpha \geq 1-1/r$ the initial graph already houses the desired perfect $K_r$-tiling). This is joint work with Jie Han and Andrew Treglown.
Host: Jie Han

April 26 E. Fiore, URI 'Spectral Characterizations of Almost Complete Graphs' by M. Camara and W. Haemers

April 19 A. Clifford, URI 'Graphs with average degree smaller than 30/11 burn slowly' by P. Pralat

April 12 M. Kowalski, URI 'Upper bounds on sets of orthogonal colorings of graphs' by Serge C. Ballif
Abstract:    In a recent article, Serge C. Ballif took the notion of orthogonal latin squares and generalized it to other latin structures by considering orthogonal colorings of graphs. In my talk I will define orthogonal colorings and provide many examples. I will also be presenting Ballif's upper bounds of the possible number of mutually orthogonal colorings of a graph and applying them to various latin structures.

March 29 J. Kim, Mathematics Institute, University of Warwick On the exponents of Turan numbers
Abstract:    The extremal number $ex(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $ex(n , F) = \Theta(n^r)$. Erdos and Simonovits conjectured that every rational number in $[1,2]$ is realisable. We show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known realisable numbers. This is joint work with Dong Yeap Kang and Hong Liu.
Host: Jie Han

March 22 M. Barrus, URI Higher connectivities for realization graphs
Abstract:    The realization graph of a degree sequence d is the graph whose vertices are the labeled realizations of d (i.e., the graphs having degree sequence d), with two of these ``realization-vertices'' adjacent exactly when the realizations can be transformed into each other by a simple edge-switching operation. It is well known that the realization graph is connected for any d. After introducing realization graphs with pictures and open questions, we'll see that all but two realization graphs are 2-connected, discuss an analogous proof for connectivity 3, comment on the possibility of a 4-connected analogue, and conjecture a 5-connected version (and beyond).

March 1 J. Guillaume, URI Closure under Majorization
Abstract:    Consider the set of partitions of a positive integer $n$ and implement an arrangement or ordering of its members using the following relation: Given two nonnegative integer sequences $d= (d_1, \cdots, d_n)$ and $e = (e_1, \cdots , e_p)$ where $d_i, e_i \geq 1,$ we say that $d$ majorizes $e$, denoted $d \succeq e$, if the terms of $d$ and $e$ add up to a common sum, and the partial sums of $d$ are always greater than or equal to the corresponding partial sums of $e.$ This majorization relation gives rise to a poset or partially ordered set called the dominance order and where the graphic partition(s) are known to form an ideal or downward closed set [Ruch & Gutman, 1979]. Furthermore, Merris showed in 2002 that degree sequences of split graphs form an ``upwards-closed" set in the dominance order. The same is true for threshold graphs. Coincidentally, these classes of graphs are known to possess some very nice properties. To give context to these examples and better understand how degree sequences of classes of graphs situate themselves in the dominance order, I will define what it means for a collection of graphs ${\mathcal F}$ to be dominance monotone and proceed to characterize the dominance monotone sets ${\mathcal F}$ for ``small'' families ${\mathcal F}$.

February 1 J. Han, URI The number of Gallai colorings
Abstract:    An edge coloring of the complete graph $K_n$ is called a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle in which all three edges have distinct colors. Given a set of $k$ colors and integer $n$, we are interested in the number of Gallai colorings of $K_n$ with colors from the given set. In particular, we show that for $k$ at most exponential in $n$, namely, $k < 2^{n/4300}$, almost all Gallai colorings use at most $2$ colors. Interestingly, this statement fails for $k > 2^{n/2}$.
This is joint work with Josefran O. Bastos and Fabricio S. Benevides (University of Ceara, Brazil).

Fall 2018

December 7 N. Townsend, URI Cops and Robbers with a Fast Robber
Abstract:    In the game of Cops and Robbers, a team of cops and a robber take turns moving on the vertex set of a connected graph. If a cop occupies the same vertex as the robber, then the cops win; if the robber can evade the cops indefinitely, then he wins. We cover the results of a thesis by Abbas Mehrabian, which focuses on the variant where the robber can traverse more than one edge on a single turn. Mehrabian categorizes all graphs on which one cop can win, and provides some lower bounds for the number of cops needed to catch a "fast" robber on varying types of n-vertex graphs.

November 9 M. Schacht, Yale Univesity and Universitaet Hamburg Homomorphism threshold for graphs
Abstract:    The interplay of minimum degree and 'structural properties' of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree $>\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of the chromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles.
Host: Jie Han

November 2 M. Barrus, URI Connecting induced subgraphs and the adjacency spectrum of a graph
Abstract:    Spectral graph theory considers relationships between properties of graphs and the eigenvalues and eigenvectors of the graphs' adjacency matrices (or other similarly defined matrices). Some well known classes of graphs, such as bipartite graphs, have complete characterizations in terms of adjacency spectra. In this talk we will examine graph classes that, like the bipartite graphs, have both spectral characterizations and forbidden induced subgraph characterizations. After some examples and preliminaries, we will present a recent result of Jiang and Polyanskii on the number of forbidden subgraphs for the class of graphs with bounded spectral radius. We will conclude by discussing graph classes characterized by their adjacency spectra and, independently, by a single forbidden induced subgraph.

October 26 M. Tait, Carnegie Mellon University Using random polynomials in extremal graph theory
Abstract:    For a fixed integer $k$ we consider the problem of how many edges may be in an $n$-vertex graph where no pair of vertices have $t$ internally disjoint paths of length $k$ between them. When $t=2$ this is the notorious even cycle problem. We show that such a graph has at most $c_k t^{1-1/k}n^{1+1/k}$ edges, and we use graphs constructed via random polynomials to show that the dependence on $t$ is correct when $k$ is odd.

October 19 E. Peterson, URI Rectangle Visibility Numbers of Graphs
Abstract:    Very-Large-Scale-Integration (VLSI) in circuitry design is the arrangement of components on the surface of a physical chip and the layout of a wiring network between components. Designing such a system can be loosely modeled in a graph theoretic setting where the components are vertices and the wires are edges. A graph with a t-rectangle visibility representation is one whose vertices can be assigned to at most t rectangles with physical area in the plane such that each edge can be assigned to either a horizontal or vertical uninterrupted channel. We call the rectangle visibility number of a graph the minimum value of t for which G has a t-rectangle visibility representation. In this talk, we will explore rectangle visibility numbers of trees and complete graphs and explore physical layouts of these graphs.

September 29 Discrete Math Day at the University of Rhode Island.

June 7	P. Morris, Freie Universitaet Berlin	Tilings in randomly perturbed graphs: bridging the gap between Hajnal--Szemer\'edi and Johansson--Kahn--Vu
		Abstract: A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together cover all the vertices in $G$. In this paper we consider perfect $K_r$-tilings in the setting of randomly perturbed graphs; a model introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it. Specifically, given any fixed $0< \alpha <1-1/r$ we determine how many random edges one must add to an $n$-vertex graph $G$ of minimum degree $\delta (G) \geq \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$-tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumps' at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $\alpha =0$) and that of Hajnal and Szemer\'edi (which demonstrates that for $\alpha \geq 1-1/r$ the initial graph already houses the desired perfect $K_r$-tiling). This is joint work with Jie Han and Andrew Treglown. Host: Jie Han
April 26	E. Fiore, URI	'Spectral Characterizations of Almost Complete Graphs' by M. Camara and W. Haemers

April 19	A. Clifford, URI	'Graphs with average degree smaller than 30/11 burn slowly' by P. Pralat

April 12	M. Kowalski, URI	'Upper bounds on sets of orthogonal colorings of graphs' by Serge C. Ballif
		Abstract: In a recent article, Serge C. Ballif took the notion of orthogonal latin squares and generalized it to other latin structures by considering orthogonal colorings of graphs. In my talk I will define orthogonal colorings and provide many examples. I will also be presenting Ballif's upper bounds of the possible number of mutually orthogonal colorings of a graph and applying them to various latin structures.
March 29	J. Kim, Mathematics Institute, University of Warwick	On the exponents of Turan numbers
		Abstract: The extremal number $ex(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $ex(n , F) = \Theta(n^r)$. Erdos and Simonovits conjectured that every rational number in $[1,2]$ is realisable. We show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known realisable numbers. This is joint work with Dong Yeap Kang and Hong Liu. Host: Jie Han
March 22	M. Barrus, URI	Higher connectivities for realization graphs
		Abstract: The realization graph of a degree sequence d is the graph whose vertices are the labeled realizations of d (i.e., the graphs having degree sequence d), with two of these ``realization-vertices'' adjacent exactly when the realizations can be transformed into each other by a simple edge-switching operation. It is well known that the realization graph is connected for any d. After introducing realization graphs with pictures and open questions, we'll see that all but two realization graphs are 2-connected, discuss an analogous proof for connectivity 3, comment on the possibility of a 4-connected analogue, and conjecture a 5-connected version (and beyond).
March 1	J. Guillaume, URI	Closure under Majorization
		Abstract: Consider the set of partitions of a positive integer $n$ and implement an arrangement or ordering of its members using the following relation: Given two nonnegative integer sequences $d= (d_1, \cdots, d_n)$ and $e = (e_1, \cdots , e_p)$ where $d_i, e_i \geq 1,$ we say that $d$ majorizes $e$, denoted $d \succeq e$, if the terms of $d$ and $e$ add up to a common sum, and the partial sums of $d$ are always greater than or equal to the corresponding partial sums of $e.$ This majorization relation gives rise to a poset or partially ordered set called the dominance order and where the graphic partition(s) are known to form an ideal or downward closed set [Ruch & Gutman, 1979]. Furthermore, Merris showed in 2002 that degree sequences of split graphs form an ``upwards-closed" set in the dominance order. The same is true for threshold graphs. Coincidentally, these classes of graphs are known to possess some very nice properties. To give context to these examples and better understand how degree sequences of classes of graphs situate themselves in the dominance order, I will define what it means for a collection of graphs ${\mathcal F}$ to be dominance monotone and proceed to characterize the dominance monotone sets ${\mathcal F}$ for ``small'' families ${\mathcal F}$.
February 1	J. Han, URI	The number of Gallai colorings
		Abstract: An edge coloring of the complete graph $K_n$ is called a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle in which all three edges have distinct colors. Given a set of $k$ colors and integer $n$, we are interested in the number of Gallai colorings of $K_n$ with colors from the given set. In particular, we show that for $k$ at most exponential in $n$, namely, $k < 2^{n/4300}$, almost all Gallai colorings use at most $2$ colors. Interestingly, this statement fails for $k > 2^{n/2}$. This is joint work with Josefran O. Bastos and Fabricio S. Benevides (University of Ceara, Brazil).

December 7	N. Townsend, URI	Cops and Robbers with a Fast Robber
		Abstract: In the game of Cops and Robbers, a team of cops and a robber take turns moving on the vertex set of a connected graph. If a cop occupies the same vertex as the robber, then the cops win; if the robber can evade the cops indefinitely, then he wins. We cover the results of a thesis by Abbas Mehrabian, which focuses on the variant where the robber can traverse more than one edge on a single turn. Mehrabian categorizes all graphs on which one cop can win, and provides some lower bounds for the number of cops needed to catch a "fast" robber on varying types of n-vertex graphs.
November 9	M. Schacht, Yale Univesity and Universitaet Hamburg	Homomorphism threshold for graphs
		Abstract: The interplay of minimum degree and 'structural properties' of large graphs with a given forbidden subgraph is a central topic in extremal graph theory. For a given graph $F$ we define the homomorphism threshold as the infimum $\alpha$ such that every $n$-vertex $F$-free graph $G$ with minimum degree $>\alpha n$ has a homomorphic image $H$ of bounded size (independent of $n$), which is $F$-free as well. Without the restriction of $H$ being $F$-free we recover the definition of the chromatic threshold, which was determined for every graph $F$ by Allen et al. The homomorphism threshold is less understood and we present recent joint work with O. Ebsen on the homomorphism threshold for odd cycles. Host: Jie Han
November 2	M. Barrus, URI	Connecting induced subgraphs and the adjacency spectrum of a graph
		Abstract: Spectral graph theory considers relationships between properties of graphs and the eigenvalues and eigenvectors of the graphs' adjacency matrices (or other similarly defined matrices). Some well known classes of graphs, such as bipartite graphs, have complete characterizations in terms of adjacency spectra. In this talk we will examine graph classes that, like the bipartite graphs, have both spectral characterizations and forbidden induced subgraph characterizations. After some examples and preliminaries, we will present a recent result of Jiang and Polyanskii on the number of forbidden subgraphs for the class of graphs with bounded spectral radius. We will conclude by discussing graph classes characterized by their adjacency spectra and, independently, by a single forbidden induced subgraph.
October 26	M. Tait, Carnegie Mellon University	Using random polynomials in extremal graph theory
		Abstract: For a fixed integer $k$ we consider the problem of how many edges may be in an $n$-vertex graph where no pair of vertices have $t$ internally disjoint paths of length $k$ between them. When $t=2$ this is the notorious even cycle problem. We show that such a graph has at most $c_k t^{1-1/k}n^{1+1/k}$ edges, and we use graphs constructed via random polynomials to show that the dependence on $t$ is correct when $k$ is odd.
October 19	E. Peterson, URI	Rectangle Visibility Numbers of Graphs
		Abstract: Very-Large-Scale-Integration (VLSI) in circuitry design is the arrangement of components on the surface of a physical chip and the layout of a wiring network between components. Designing such a system can be loosely modeled in a graph theoretic setting where the components are vertices and the wires are edges. A graph with a t-rectangle visibility representation is one whose vertices can be assigned to at most t rectangles with physical area in the plane such that each edge can be assigned to either a horizontal or vertical uninterrupted channel. We call the rectangle visibility number of a graph the minimum value of t for which G has a t-rectangle visibility representation. In this talk, we will explore rectangle visibility numbers of trees and complete graphs and explore physical layouts of these graphs.
September 29		Discrete Math Day at the University of Rhode Island.