Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2016

April 29 S. O'Reilly, URI Report on ' On the approximate Shape of Degree Sequences that are Not Potentially H-graphic' by C. Erbes, M. Ferrara, R. Martin, P. Wenger
Abstract: In 1970, Erdős showed that for any $K_{r+1}$-free graph H, there exists an r-partite graph G such that $\pi(G)$ majorizes $\pi(H)$. In 2005, Pikhurko and Taraz generalized this notion and showed that for any graph F with chromatic number $r+1$, the degree sequence of an F-free graph is, in an appropriate sense, nearly majorized by the degree sequence of an r-partite graph.
In the paper of Catherine Erbes, Michael Ferrara, Ryan Martin, and Paul Wenger, they give similar results for degree sequences that are not potentially H-graphic. In particular, there is a graphic sequence $\pi^\ast(H)$ such that if $\pi$ is a graphic sequence that is not potentially H-graphic, then $\pi$ is close to being majorized by $\pi^\ast(H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $\pi^\ast(H)$ asymptotically gives the maximum possible sum of a graphic sequence $\pi$ that is not potentially H-graphic.
In this talk I will introduce this area of graph theory and will present the main results of the paper.

April 22 J. Guillaume, URI Families of Pairs of Graphs with a Large Number of Common Cards: a Variant of the Reconstruction Problem
Abstract: The Reconstruction Conjecture (RC) certainly needs no introduction in graph theory circles. Besides being more than half a century old, its notoriety is in part due to its unrelenting resistance to continuous valliant efforts of many graph theorists to solve it. The RC states that any finite, undirected, simple graph G on at least three vertices is detemined, up to isomorphism, by its deck, which is the collection of its vertex-deleted subgraphs. Though the RC remains unresolved, significant work has been done in related reconstruction problems. One of these related areas of research is the area of subdeck reconstruction, which is, for example, concerned with the universal reconstruction number, denoted urn(G). By definition, urn(G) is the minimum k such that G is reconstructible from any subdeck of size k. In a paper titled "Families of Pairs of Graphs with a Large Number of Common Cards" (Journal of Graph Theory,2009), Andrew Bowler and others redefine urn(G) in terms of the maximum number of cards between pairs of non-isomorphic graphs, which is calculated for infinite family of carefully and arbitrarily constructed pairs of graphs. They are able to come up with a new maximum for the number of common cards between non-isomorphic pairs of graphs and, thereby, upset the previous bounds conjectured by Myrvold in 1990. Hence, a modification of Myrvold's Conjecture, together with a stronger version of the RC, emerges.

Fall 2015

December 2 J. Sinkovic, C&O Dept., University of Waterloo The minimum rank problem for a graph
Abstract:    Matrices and graphs have a natural relationship in discrete mathematics. The adjacency matrix and Laplacian matrix of a graph have been studied intensely. Their eigenvalues have been found to hold a lot of information about the graph. For example, they can determine the number of spanning trees, whether a graph is bipartite, or in some cases planarity.
Both the adjacency matrix and the Laplacian matrix belong to a large family of real symmetric matrices determined by a graph. The off-diagonal entries of such matrices are required to be zero in the absence of an edge and nonzero in the presence of an edge. One of the problems of interest is determining the maximum multiplicity of an eigenvalue of a matrix in the family. I will share some results concerning this question in relation to outerplanar graphs.

November 20 M. Barrus, URI Degree Sequences, Forced Adjacency Relationships, and Weakly Threshold Graphs
Abstract:    Degree sequences of graphs usually have several labeled realizations with differing edge sets. In some cases, however, vertices with certain degrees are adjacent (or non-adjacent) in every realization. The quintessential example of this occurs with a threshold graph, where every adjacency relationship is uniquely determined by the degree sequence.
Given a degree sequence, we characterize degree pairs corresponding to vertices that are forcibly (non)-adjacent, revealing connections with the Erdos-Gallai inequalities and the majorization order on degree sequences, as well as with a structural decomposition of graphs due to Tyshkevich. Exploring these connections further naturally leads us to define the class of weakly threshold graphs. We summarize a few of the ways in which these graphs generalize properties of threshold graphs in pleasing ways.

November 13 R. Gouveia, URI Cyclic base orderings and uniformly dense networks
Abstract:    One of the principle areas of interest in graph theory is analysis of networks and their strengths. Our research looks at a proposed method of determining which networks are uniformly dense. A graph is a collection of points called vertices and lines called edges connecting some pairs of vertices. A cycle occurs in a graph when its edges form a closed loop. A cyclic ordering of the edges of a graph is any way to list all the edges such that the first follows the last. For a network modeled as a graph $G$, we define a quantity $h(G)$ as the largest number of consecutive edges in an ordering where the edges do not form a cycle. Kajitani conjectures in Discrete Math., 72 (1988), 187--194, that a connected network $G$ is uniformly dense if and only if $h(G) = n-1$, where n is the number of nodes in $G$. Our research places bounds on $h(G)$ for a few infinite classes of graphs. Joint work with Jonathan D. Ashbrock and Hong-Jian Lai.

October 30 W. Kinnersley, URI Random-player Maker-Breaker games by Krivilevich and Kronenberg
Abstract:    For traditional Maker-Breaker games, the "Erdos paradigm" suggests that, in an asymptotic sense, the outcome when both players play optimally is often the same as when both play randomly. What happens when only one player plays randomly, and the other is allowed to play "intelligently"? We explore this question for several classical Maker-Breaker games, namely those in which Maker seeks to build a Hamiltonian cycle, a perfect matching, and a k-edge-connected graph.

September 25 L. Thoma, URI Maker-Breaker games

April 29	S. O'Reilly, URI	Report on ' On the approximate Shape of Degree Sequences that are Not Potentially H-graphic' by C. Erbes, M. Ferrara, R. Martin, P. Wenger
		Abstract: In 1970, Erdős showed that for any $K_{r+1}$-free graph H, there exists an r-partite graph G such that $\pi(G)$ majorizes $\pi(H)$. In 2005, Pikhurko and Taraz generalized this notion and showed that for any graph F with chromatic number $r+1$, the degree sequence of an F-free graph is, in an appropriate sense, nearly majorized by the degree sequence of an r-partite graph. In the paper of Catherine Erbes, Michael Ferrara, Ryan Martin, and Paul Wenger, they give similar results for degree sequences that are not potentially H-graphic. In particular, there is a graphic sequence $\pi^\ast(H)$ such that if $\pi$ is a graphic sequence that is not potentially H-graphic, then $\pi$ is close to being majorized by $\pi^\ast(H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $\pi^\ast(H)$ asymptotically gives the maximum possible sum of a graphic sequence $\pi$ that is not potentially H-graphic. In this talk I will introduce this area of graph theory and will present the main results of the paper.
April 22	J. Guillaume, URI	Families of Pairs of Graphs with a Large Number of Common Cards: a Variant of the Reconstruction Problem
		Abstract: The Reconstruction Conjecture (RC) certainly needs no introduction in graph theory circles. Besides being more than half a century old, its notoriety is in part due to its unrelenting resistance to continuous valliant efforts of many graph theorists to solve it. The RC states that any finite, undirected, simple graph G on at least three vertices is detemined, up to isomorphism, by its deck, which is the collection of its vertex-deleted subgraphs. Though the RC remains unresolved, significant work has been done in related reconstruction problems. One of these related areas of research is the area of subdeck reconstruction, which is, for example, concerned with the universal reconstruction number, denoted urn(G). By definition, urn(G) is the minimum k such that G is reconstructible from any subdeck of size k. In a paper titled "Families of Pairs of Graphs with a Large Number of Common Cards" (Journal of Graph Theory,2009), Andrew Bowler and others redefine urn(G) in terms of the maximum number of cards between pairs of non-isomorphic graphs, which is calculated for infinite family of carefully and arbitrarily constructed pairs of graphs. They are able to come up with a new maximum for the number of common cards between non-isomorphic pairs of graphs and, thereby, upset the previous bounds conjectured by Myrvold in 1990. Hence, a modification of Myrvold's Conjecture, together with a stronger version of the RC, emerges.

December 2	J. Sinkovic, C&O Dept., University of Waterloo	The minimum rank problem for a graph
		Abstract: Matrices and graphs have a natural relationship in discrete mathematics. The adjacency matrix and Laplacian matrix of a graph have been studied intensely. Their eigenvalues have been found to hold a lot of information about the graph. For example, they can determine the number of spanning trees, whether a graph is bipartite, or in some cases planarity. Both the adjacency matrix and the Laplacian matrix belong to a large family of real symmetric matrices determined by a graph. The off-diagonal entries of such matrices are required to be zero in the absence of an edge and nonzero in the presence of an edge. One of the problems of interest is determining the maximum multiplicity of an eigenvalue of a matrix in the family. I will share some results concerning this question in relation to outerplanar graphs.
November 20	M. Barrus, URI	Degree Sequences, Forced Adjacency Relationships, and Weakly Threshold Graphs
		Abstract: Degree sequences of graphs usually have several labeled realizations with differing edge sets. In some cases, however, vertices with certain degrees are adjacent (or non-adjacent) in every realization. The quintessential example of this occurs with a threshold graph, where every adjacency relationship is uniquely determined by the degree sequence. Given a degree sequence, we characterize degree pairs corresponding to vertices that are forcibly (non)-adjacent, revealing connections with the Erdos-Gallai inequalities and the majorization order on degree sequences, as well as with a structural decomposition of graphs due to Tyshkevich. Exploring these connections further naturally leads us to define the class of weakly threshold graphs. We summarize a few of the ways in which these graphs generalize properties of threshold graphs in pleasing ways.
November 13	R. Gouveia, URI	Cyclic base orderings and uniformly dense networks
		Abstract: One of the principle areas of interest in graph theory is analysis of networks and their strengths. Our research looks at a proposed method of determining which networks are uniformly dense. A graph is a collection of points called vertices and lines called edges connecting some pairs of vertices. A cycle occurs in a graph when its edges form a closed loop. A cyclic ordering of the edges of a graph is any way to list all the edges such that the first follows the last. For a network modeled as a graph $G$, we define a quantity $h(G)$ as the largest number of consecutive edges in an ordering where the edges do not form a cycle. Kajitani conjectures in Discrete Math., 72 (1988), 187--194, that a connected network $G$ is uniformly dense if and only if $h(G) = n-1$, where n is the number of nodes in $G$. Our research places bounds on $h(G)$ for a few infinite classes of graphs. Joint work with Jonathan D. Ashbrock and Hong-Jian Lai.
October 30	W. Kinnersley, URI	Random-player Maker-Breaker games by Krivilevich and Kronenberg
		Abstract: For traditional Maker-Breaker games, the "Erdos paradigm" suggests that, in an asymptotic sense, the outcome when both players play optimally is often the same as when both play randomly. What happens when only one player plays randomly, and the other is allowed to play "intelligently"? We explore this question for several classical Maker-Breaker games, namely those in which Maker seeks to build a Hamiltonian cycle, a perfect matching, and a k-edge-connected graph.
September 25	L. Thoma, URI	Maker-Breaker games