Graph Theory Seminar
Upcoming Events
Past Events
Nov. 5, 2024
presented by Emma Jent at 10 a.m. in the Alavi Commons 6625 Everett Tower
Oct. 29, 2024
presented by Emma Jent at 10 a.m. in the Alavi Commons 6625 Everett Tower
Oct. 22, 2024
presented by Linda Lesniak at 10 a.m. in the Alavi Commons 6625 Everett Tower
Oct. 15, 2024
presented by Gabriela Araujo-Pardo from Universidad Nacional Aut´onoma de M´exico, Campus Juriquilla, Quer´etaro. M´exico
Feb. 5, 2020
The so-called differential equation method in probabilistic combinatorics presented by Patrick Bennett, Ph.D., Department of Mathematics, Western Michigan University
Abstract: Differential equations inherently belong to the realm of continuous mathematics, but often they are used to describe discrete objects. For example, we use differential equations to model population growth (and the size of a population is always an integer). In this talk I will describe a general method for proving that certain random processes are overwhelmingly likely to evolve in a way that is very closely approximated by a solution to a system of differential equations. Several examples will be discussed.
Jan. 29, 2020
Anti-van der Waerden numbers on Trees presented by Elizabeth Sprangel, Iowa State University
Abstract: In this talk, arithmetic progressions on the integers and the integers modulo n are extended to graphs. This allows for the definition of the anti-van derWaerden number of a graph, which is the least positive integer r such that every exact r-coloring of a graph contains a rainbow k-term arithmetic progression. We will discuss bounds on the anti-van der Waerden number on trees regarding 3-term arithmetic progressions.
Jan. 15, 2020
Hamiltonian Berge Cycles in Random Hypergraphs presented by Deepak Bal, Ph.D., Montclair State University
Abstract: A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges (v1, e1, ... , vn, en) where vi+1 are in ei for each i (indices considered modulo n), and a Hamiltonian Berge cycle is one in which every vertex appears. In this talk we will discuss the threshold probability for when a random r-uniform hypergraph is likely to contain such a cycle. This is joint work with Pat Devlin, Ross Berkowitz and Mathias Schacht.
Nov. 20, 2019
Te size-Ramsey number of a path presented by Louis DeBiasio, Ph.D., Miami University
Abstract: Given a graph H, the size-Ramsey number of H is the minimum m such that there exists a graph G with m edges such that in every 2-coloring of G, there exists a monochromatic copy of H. Perhaps due to the fact that Paul Erdös offered $100 simply to determine the correct order of magnitude, getting bounds on the size-Ramsey number of Pn, the path on n vertices, is the most well-studied case. It is known that the size-Ramsey number of Pn is between (2.5 - o(1))n and 74n, with the current best upper and lower bounds both due to Dudek and Pralat.
We prove that every graph with at most (3.75 - o(1))n edges has a 2-coloring such that there are no monochromatic Pn's, which shows that the size-Ramsey number of Pn is at least (3.75 - o(1))n. We also discuss the r-color version of the problem.
Joint work with Deepak Bal.
Nov. 14, 2019
Maximum Crossing Numbers of Trees and Weighted Turan Numbers presented by Sean English, Ph.D., Department of Mathematics, University Of Illinois At Urbana-Champaign
3 p.m.
Nov. 6, 2019
Alternating Connectivity in Random Graphs, Part II presented by Ryan Cushman, Department of Mathematics, Western Michigan University
Abstract: This talk will be a continuation of last week's talk. In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. For example, it is advantageous to find codes in which code words do not share many corresponding digits (i.e. code words have a large Hamming distance). Thus, one may ask what the maximum n is such that there exists a code of n code words with a fixed alphabet, code words with m digits, and minimum Hamming distance t. We can translate this context into the language of complete bipartite graphs Km,n. In this translation, finding the Hamming distance between two code words corresponds to counting the number of alternating paths between corresponding vertices. Bennett, Dudek, and LaForge considered a related problem of maximizing the number of internally disjoint alternating paths between any two vertices in a certain partition set. In this talk, we discuss the current state of the question as well as a generalization for G(n,p).
Oct. 30, 2019
Alternating Connectivity in Random Graphs presented by Ryan Cushman, Department of Mathematics, Western Michigan University
Abstract: In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. For example, it is advantageous to find codes in which code words do not share many corresponding digits (i.e. code words have a large Hamming distance). Thus, one may ask what the maximum n is such that there exists a code of n code words with a fixed alphabet, code words with m digits, and minimum Hamming distance t. We can translate this context into the language of complete bipartite graphs Km,n. In this translation, finding the Hamming distance between two code words corresponds to counting the number of alternating paths between corresponding vertices. Bennett, Dudek, and LaForge considered a related problem of maximizing the number of internally disjoint alternating paths between any two vertices in a certain partition set. In this talk, we discuss the current state of the question as well as a generalization for G(n,p).
Oct. 9, 2019
Bears versus the demon on Kn,n, part II presented by Patrick Bennett, Ph.D., Department of Mathematics, Western Michigan University
Abstract: In this talk we will finish describing a strategy for the bears in the Hat Guessing Game (the game is described below), which appeared in a recent paper by Alon, Ben-Eliezer, Shangguan and Tamo. Last week we proved that the existence of certain matrices would imply a strategy for the bears on Kn,n. We say a q-ary matrix is t-saturated of for every set T of t columns there exists a row in which the columns of T have every entry in {1,...,q}. We will prove the existence of t-saturated q-ary matrices of a suitable dimension to be used for a strategy for the bears in the Hat Guessing Game. Then, time permitting, we will discuss ideas for the Hat Guessing Game on Kn,n,n.
The Hat Guessing Game is as follows: There are n bears and one demon (who can read the bears' minds), and the bears are each sitting on one vertex of a graph G. The bears close their eyes and the demon chooses one colored hat for each bear, where each hat can be one of q different colors. The bears open their eyes and they can see the hats of their neighbors (in G). Without communicating with each other, the bears will now each guess the color of their own hats. The guesses are made simultaneously so one bear's guess cannot depend on another's. The bears win if any of them guess correctly; the demon wins if the bears are all incorrect. Clearly the bears have a winning strategy if q = 1, and last week we showed the demon has a winning strategy if q > n. We define HG(G) to be the largest q such that the bears win.
Oct. 2, 2019
Bears versus the demon on K presented by Patrick Bennett, Ph.D., Department of Mathematics, Western Michigan University
Abstract: consider the following puzzle. Suppose there are n bears and one demon (who can read the bears' minds). The bears close their eyes and the demon chooses one colored hat for each bear, where each hat can be one of q different colors. The bears open their eyes and they can see all the other bears hats, but not their own hat. Without communicating with each other, the bears will now each guess the color of their own hats. The guesses are made simultaneously so one bear's guess cannot depend on another's. The bears win if any of them guess correctly; the demon wins if the bears are all incorrect. In this situation, it is known that the bears have a winning strategy if and only if q ≤ n.
In 2008, Butler, Hajiaghayi, Kleinberg and Leighton generalized the above puzzle. Now we suppose each bear sits at a vertex in a graph, and the bears can only see their neighbors' hats. We can now ask for any graph, what is the maximum q for which the bears have a winning strategy. In this talk we will try to focus on the case where the graph is Kn,n and a new lower bound proved by Alon, Ben-Eliezer, Shangguan and Tamo.
Sept. 18, 2019
Combinatorial Nullstellensatz presented by Patrick Bennett, Ph.D., Department of Mathematics, Western Michigan University
Abstract: In 1999, Noga Alon proved the combinatorial Nullstellensatz (a theorem about the zeroes of polynomials over fields) and gave some surprising applications. In this talk we will state the Nustellensatz and then see several of these applications.
Sept. 11, 2019
Long monochromatic paths in random graphs presented by Andrzej Dudek, Ph.D., Department of Mathematics, Western Michigan University
Abstract: Recall that the size-Ramsey number of F, r^(F, r), is the smallest integer m such that there exists a host graph G with m edges such that any r-edge coloring of G yields a monochromatic copy of F. In this talk, we are concerned with the size-Ramsey numbe3r of the path Pn on n vertices. First, we explore some recent developments regarding r^(Pn, r). Next, we study a Turán problem involving random graphs G(N, p), the best-known host graphs for Pn. To that end, we consider the random variable ex(G(N, p), Pn), the maximum number of edges in a Pn-free subgraph of G(N, p). The latter is a joint work with József Balogh and Lina Li (University of Illinois at Urbana-Champaign).