Discrete Mathematics Seminar
Fall 2017
November 15 | A. Bonato, Ryerson University | Burning spiders and path forests |
Abstract:
Graph burning is a simplified model for the
spread of memes and contagion in social networks. A fire
breaks out in each time-step and spreads to its neighbours.
The burning number of a graph measures the number of
time-steps it takes so that all vertices are burning.
While it is conjectured that the burning number of
a connected graph of order n is a most the ceiling of the
square root of n, this remains open in general. We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3/2-approximation algorithm for computing the burning number of path-forests. Host: Bill Kinnersley |
||
November 10 | J. Guillaume, URI | The Distinguishing Number and Distinguishing Chromatic Number of a Graph |
Abstract: Let's say we have a ring of $n$ seemingly identical keys, which are assigned to different doors, and our goal is to be able to distinguish them using a variety of handle shapes. From the point of view of graph theory, this is finding out how many labels (colors) are needed to distinguish the vertices of $C_n$, so that the only label-preserving (color-preserving) automorphism of $C_n$ is the identity. Extending this idea to any graph $G$, we want, in other words, label the vertices in a way that destroys the symmetries of the graph. Let $r$ be the number of labels used to accomplish this goal; we thus say that $G$ has an $r$-distinguishing labeling and the distinguishing number of $G$, denoted $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling. Furthermore, if we attain this objective using a proper labeling (coloring), then we call the minimum $r$, the distinguishing chromatic number of $G$. From this talk, the audience will learn about the history (which is very recent), known results (surprising to say the least), and open questions related to both concepts. Our independent study project on this topic and early results will also be discussed. | ||
November 3 | M. Barrus, URI | Independence number and the Havel-Hakimi Residue |
Abstract: The Havel-Hakimi algorithm begins with the degree sequence of a graph and iteratively reduces it to a list of zeroes. The number of zeroes produced, known as the residue, is a lower bound on the independence number of the graph. We discuss the tightness of the bound from a few perspectives, first in the situation in which the degree sequence does not have many realizations, and second in the situation where the graph's structure allows a vertex deletion sequence that mimics the Havel-Hakimi process. | ||
October 27 | L. Thoma, URI | Edge density, homomorphisms, and correlations: combinatorics and analysis |
October 20 | W. Kinnersley, URI | Bounds on the length of a game of Cops and Robbers |
Spring 2017
April 28 | M. Williams, URI | Report on 'Unavoidable Induced Subgraphs in Large Graphs with no Homogeneous Sets' by M. Chudnovsky, R. Kim, S. Oum, P. Seymour |
April 7 | J. Erickson, URI | Waiter-Client and Client-Waiter Hamiltonicity Games on Random Graphs |
Abstract: The theory of positional games on graphs has developed into a highly studied area of combinatorics. In this talk, I'll explain the basics of two types of positional games played on graphs---the Waiter-Client and Client-Waiter games---and introduce the concepts of random graphs, expanders, and boosters. Then, I will use these topics to prove that when played on random graphs with the winning sets of the games being Hamiltonian cycles, we can derive sharp thresholds for players' winning strategies for these games. This is a report on 'Waiter-Client and Client-Waiter Hamiltonicity games on random graphs by D. Hefetz, M. Krivelevich, and W. Tan. | ||
March 31 | M. Kempton, CMSA, Harvard University | Non-backtracking Random Walks and Polya's Recurrence Theorem |
Abstract: The theory of random walks on graphs has become a major area of study in graph theory. Random walks are the basis for many important algorithms involving graphs in the real world, and there theory has been widely studied and is largely well-understood. In recent years, the study of non-backtracking random walks has gained interest, although their analysis has proven challenging. I will give some background on non-backtracking random walks on graphs, and present a non-backtracking version of a classical theorem in the theory of random walks on graphs: Polya's recurrence theorem. Host: Michael Barrus. | ||
March 24 | M. Barrus, URI | The Grone-Merris Conjecture |
Abstract: Spectral graph theory seeks to find relationships between the eigenvalues of a graph's adjacency matrix (or other related matrices) and the properties of the graph. In particular, in 1994 Grone and Merris conjectured a relationship between the degree sequence of an arbitrary graph $G$ and the eigenvalues of the Laplacian matrix of $G$. In this talk we introduce spectral graph theory, describe the relationship between degree sequences and eigenvalues, and present highlights of Hua Bai's 2011 proof of the Grone-Merris Conjecture. |
Fall 2016
December 9 | J. Sinkovic, C&O Dept., University of Waterloo | Using eigenvalues to bound the independence number of graph |
Abstract: An independent set in a graph G is a set of pairwise non adjacent vertices and the maximum size of such a set is the independence number of G. A weight matrix W for a graph G is a symmetric (or Hermitian) matrix such that the (i,j) entry of W is zero whenever vertex i is not adjacent to vertex j. The Cvetkovic bound or inertia bound uses the eigenvalues of a weight matrix of G to give an upper bound on the independence number of a graph. We will introduce the bound, give a short proof, and discuss when the bound is tight. Until recently, it was open question as to whether the bound was always tight. Host: Michael Barrus. | ||
December 2 | E. Peterson, URI | Building Spanning Trees Quickly in Maker-Breaker Games |
November 18 | J. Guillaume, URI | A Tour of the Reconstruction Conjecture |
Abstract: The reconstruction conjecture is unequivocally one of the foremost open problems in graph theory. To start, we explore its background and history before stating it as a graph theory problem. Next, we dive into some important results regarding the conjecture, as well as different approaches considered and several variations of the problem. Finally, we take a look at what the future holds for the reconstruction conjecture and possible new directions that can be taken. | ||
November 4 | J. Jones, URI | Report on 'How to Hunt an Invisible Rabbit on a Graph' by T. Abramovskaya, F. Fomin, P. Golovach, M. Pilipczuk |
October 28 | W. Kinnersley, URI | Two variants of Cops and Robbers |
October 21 | A. Kodess, URI | Algebraically defined digraphs |
October 14 | M. Barrus, URI | Dense graphs and a conjecture for tree-depth |
Abstract: The tree-depth of a graph $G$ is the smallest number of ordered labels necessary to label the vertices of $G$ so that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is 1-unique if for each vertex $v$ in $G$, there is an optimal tree-depth-labeling of $G$ in which $v$ is the unique vertex receiving the lowest label. In a recent work the author and J. Sinkovic conjectured that all minor-minimal graphs having a fixed tree-depth are necessarily 1-unique. In this talk we study graphs with high tree-depths in relation to their orders. Using these results, a computer search, and a few interesting families of dense graphs, we resolve the 1-uniqueness conjecture and clarify relationships between 1-uniqueness and minor-minimality for tree-depth. |
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 |
Spring 2015
April 17 | J. Jones, URI | Report on Recontamination does not help to search a graph by A. LaPaugh. |
April 10 | M. Krul, Emmanuel College | Polynomial ideals and their applications to graph and hypergraph theory. |
April 03 | A. Armstrong, URI | Planar Graphs are (4,1) Choosable. A theorem by Cushing and Kierstead. |
March 27 | L. Hamel, URI | Automatic Theorem Proving: A Very Brief Introduction |
Abstract: Automatic theorem proving is interesting because it shifts the burden of proof from the user to the machine. In this talk we briefly survey the differences between fully automatic theorem provers and proof assistants. We show that the latter seems more promising as a tool because of deep theoretical limitations of the former. We then turn our attention of the field of formal programming language semantics and show that here Prolog viewed as a proof assistant works very well and has a much more gradual learning curve than some of the other well known proof assistants. | ||
March 20 | spring break | |
Feb 27, Mar 6 | job interviews | |
February 20 | M. Barrus, URI | Uniqueness and minimal obstructions for tree-depth |
February 13 | L. Thoma, URI | The regularity lemma: a proof by A. Schrijver - III |
February 6 | L. Thoma, URI | The regularity lemma: a proof by A. Schrijver - II |
January 30 | L. Thoma, URI | The regularity lemma: a proof by A. Schrijver - I |
Fall 2014
October 31 | N. Finizio, URI | ZCPS-starters: necessary and sufficient conditions for the existence of ZCPS-whist designs |
October 15 | D. Cranston | Painting squares of graphs with $\Delta^2-1$ colors |
Virginia Commonwealth University | Abstract: Brooks' Theorem states that if $G$ is a connected graph with maximum degree $\Delta$ at least 3, then $G$ can be colored with $\Delta$ colors. This result has been generalized to list-coloring and more general contexts. The square $G^2$ of a graph $G$ is formed from $G$ by adding an edge between each pair of vertices at distance two. When $G$ has maximum degree $\Delta$, it is easy to show that $G^2$ has maximum degree at most $\Delta^2$; so Brooks' Theorem implies that $G^2$ can be colored with $\Delta^2$ colors. Cranston and Kim conjectured that we can improve this upper bound by at least 1. Specifically, they conjectured that $\chi_{\ell}(G^2) \le \Delta^2-1$ unless $G$ is a Moore graph (here $\chi_{\ell}$ denotes the list chromatic number). We prove their conjecture and survey some harder conjectures about coloring squares of graphs. This is joint work with Landon Rabern. | |
October 3 | L. Thoma, URI | Semigroups, quasi-orders, and some applications |
September 26 | M. Barrus, URI | The polytope of fractional realizations of degree sequences |
Abstract: Fractional graph theory takes familiar graph-theoretic parameters and structures and studies what happens when the associated numbers are no longer required to be integers. In this talk, I will introduce a convex polytope that arises when we study "fractional" realizations of the degree sequence of a simple graph. After observing how closely the vertices of the polytope mimic traditional degree sequence realizations in general, we will see that for a certain class of graphs (the decisive graphs) the correspondence is exact. We describe the structure of the decisive graphs and their degree sequences and show that many properties of threshold graphs and split graphs can be generalized to properties that characterize all decisive graphs. | ||
September 19 | W. Kinnersley, URI | Degree ramsey and online degree ramsey numbers |
September 12 | A. Kodess, URI | Properties of some algebraically defined digraphs |