Graph Theory Seminar

The Department of Mathematics at Western Michigan University will present a graph theory seminar on Fridays.

Day and time: Wednesdays, 2 p.m.
Place: 6625 Everett Tower

Spring 2020

feb. 5

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. 15

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.

Fall 2019

nov. 20

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.

Thursday, Nov. 14

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

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 codewords do not share many corresponding digits (i.e. codewords have a large Hamming distance). Thus, one may ask what the maximum n is such that there exists a code of n codewords with a fixed alphabet, codewords 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 codewords 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

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 codewords do not share many corresponding digits (i.e. codewords have a large Hamming distance). Thus, one may ask what the maximum n is such that there exists a code of n codewords with a fixed alphabet, codewords 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 codewords 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

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

Bears versus the demon on Kn,n 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 anothers. 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

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

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).