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

Fall 2019

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