Graph Theory Seminar

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

Day and time: Fridays, 3 to 3:50 p.m.
Place: 3307 Rood Hall

Fall 2017

nov. 17

Biplanes: an introduction presented by Mohammad Shatnawi, Department of Mathematics, Western Michigan University

Abstract: Balanced incomplete block designs have been used in the design of experiments; agricultural experiments, medical experiments, and others. Formall, a (b,v,k,r,λ) balanced incomplete block design is an arrangement of v distinct objects into b blocks such that each block contains exactly k distinct objects, each object occurs in exactly r different blocks, and every pair of distinct objects occurs together in precisely λ blocks. A design is symmetric if b=v and k=r. If λ=2 a symmetric design is called a biplane. Marshall Hall Jr. asked the question, "Are there only a finite number of biplanes?".

In this talk, we will, via Marshall Hall Jr., introduce biplanes and then sketch the current situation with respect to the question: "Are there only a finite number of biplanes?".

Flyer

Nov. 10

Flag algebras and applications presented by Bernard Lidický, Iowa State University

Abstract: We give a short introduction to flag algebras and we discuss several of its applications. Flag algebras is a method, developed by Razborov, to attack problems in extremal combinatorics. Razborov formulated the method in a general way which made it applicable to various settings. In this talk we give a brief introduction of the basic notions used in flag algebras and demonstrate the method on Mantel's theorem. Then we discuss applications of the flag algebras in different settings. In particular we mention applications to crossing number, iterated extremal structure and Ramsey numbers.

Flyer

oct. 27

Balanced incomplete block designs: an introduction presented by Mohammad Shatnawi, Western Michigan University

Abstract: Balanced incomplete block designs have been used in the design of experiments; agricultural experiments, medical experiments and others. Furthermore, in mathematics, they have been used in the construction of error correcting codes and in the construction of the first sporadic simple groups. Formally, a (b,v,k,r,λ) balanced incomplete block design is an arrangement of v distinct objects into b blocks such that each block contains exactly k distinct objects, each object occurs in exactly r different blocks, and every pair of distinct objects occurs together in precisely λ blocks. When do they exist and how do we construct them? In this talk, using elementary matrix theory, we will prove elementary theorems on block designs and we will give examples. Also, using finite fields, we will prove a theorem of Singer which give us a method of constructing a class of designs. An open question in the field is: if a finite projective plane has a Singer cycle is it necessarily Desarguesian?

Flyer

oct. 20

The number of paths and cycles in a digraph presented by Laars Helenius, Western Michigan University

Abstract: Let D be a digraph and let L be any k + 1 sequence of vertices from D. Then L is a simple k-sequence when it represents a path or cycle of length k in D. An algorithm is presented for constructing from the adjacency matrix A of a digraph the matrix of its simple k-sequences Ak. In this matrix aij(k) gives the number of paths starting at vi and ending at vj when i ≠ j and the number of cycles containing vi when i = j.

Flyer

oct. 13

The number of paths and cycles in a digraph presented by Laars Helenius, Western Michigan University

Abstract: Let D be a digraph and let L be any k + 1 sequence of vertices from D. Then L is a simple k-sequence when it represents a path or cycle of length k in D. An algorithm is presented for constructing from the adjacency matrix A of a digraph the matrix of its simple k-sequences Ak. In this matrix aij(k) gives the number of paths starting at vi and ending at vj when i ≠ j and the number of cycles containing vi when i = j.

Flyer

oct. 6

From graph automorphism to network alignment presented by Duy Duong-Tran, Purdue University

Abstract: Graph automorphism has a long history dated back to Frutch's Theorem (1939) which states that for every finite group χ, there exists a graph G whose automorphism group is isomorphic to χ. In this talk, we will briefly revisit Theorem 9.4 from Bol-lobás Random Graph textbook which states that given Gn,M and ½n log(n) + ω(n)n ≤ M ≤ 2n log(n), then Σ P≠1,p∈Sn I(p) = UM = o (LM) where LM, UM is the number of labelled, and unlabelled graph, respectively; I(p) is the number of graphs invariant under p ∈ Sn. On the second part of the seminar, we will use some major concepts in graph morphism to approach the so-called network alignment problem which naturally arises in applications such as protein-protein interaction or minimium bisection problem. We will show that even though graph isomorphism is generally NP-hard, certain algorithms can approximate an isomorphism efficiently. Specifically, we will revisit the quadratic assignment framework which maximizes maxS < Ga, SGbST > where S is a permutation matrix; Ga, Gb are adjacency matrices of graph Ga, Gb. Another interesting question that arises in network alignment is if we know a certain proportion of matched vertices between Ga and Gb, often represented by ω (the number of known rows/columns in the permutation matrix), does sharp transition take place in the network alignment problems? We will discuss the initial conjecture that ω = O(√n log n).

Flyer

sept. 22

The t-tone chromatic number and random graphs presented by Patrick Bennett, Western Michigan University

Abstract: First introduced by Chartrand, the t-tone chromatic number is a generalization of the standard chromatic number. For a graph G, we define the t-tone chromatic number τt(G) to be the minimum number of colors needed to assign each vertex a set of t colors, such that if two vertices u, v are at distance i ≥ 1 then u and v share at most i - 1 colors. Thus, the 1-tone chromatic number τt(G) is the same as the standard chromatic number X(G). In this talk we will discuss some of the properties of τt(G) and investigate its behavior when G is a random graph. We will see that for almost all graphs we have τt(G) ≈ t · X(G), but we will also see that this is not the case for sparse random graphs.

This talk is about joint work with Bal, Frieze and Dudek.

Flyer

sept. 15

Large monochromatic components in sparse random hypergraphs presented by Sean English, Western Michigan University

Abstract: It is know, due to Gyárfás and Füredi, that for any r-coloring of the edges of Kn, there is a monochromatic component of order (1/(r-1) + o(1))n. They also showed that this is best possible if r-1 is a prime power. Recently, Bal and DeBiasio, and independently Dudek and Pralat showed that the binomial random graph G(n,p) and arbitrarily small constant ◊ > 0, there is a monochromatic component of order (a/(r-1) -◊)n, provided that pn → ∞. As before, this result is clearly best possible.

In this talk we present a generalization of this result to hypergraphs. Specifically we show that in the k-uniform random hypergraph, H(k)(n,p) a.a.s. for any k-coloring of the edges, there is a monochromatic component of order (1 - ◊)n and for any k+1 coloring, there is a monochromatic component of order (1 - ◊) k/k+1 * n.

This project is joint work with Patrick Bennett, Louis Debiasio and Andrzej Dudek.

Flyer