Date

Speaker

Title

Abstract

Jan 13

Organizational Meeting

Jan 20

Canceled in favor of Tracy Hall's colloquium (4:10PM, 298 Carver)

Jan 27

Roger Maddux*

Feb 03

Roger Maddux*

Feb 10

Salah A. Aly*

Classical and quantum LDPC codes constructed from elements of Finite fields and finite geometries.

Low-density parity check (LDPC) codes are a significant class of classical codes with many applications. Several good LDPC codes have been constructed using random, algebraic, and finite geometries approaches, with containing cycles of length at least six in their Tanner graphs. In this talk, I introduce LDPC codes and their connection to graph theory. Then I construct a class of LDPC codes based on the elements of finite fields and finite geometries. The parity check matrices of these codes are adapted to be self-orthogonal with containing only one cycle of length four in each pair of two rows. As a consequence, a new class of quantum LDPC codes based on lines and points of finite geometries is constructed. I will assume no prior knowledge of quantum or LDPC codes.

Feb 17

Jake Manske

Frolicking in a butterfly-free meadow: on the largest set family without $A \cup B \subset C \cap D$

Feb 24

Darren Row

An introduction to number coloring: Some generalizations of Schur's Theorem

Mar 03

Michelle Lastrina

Planar 5-list coloring: Non-extendability at distance 4.

Mar 10

Maria Axenovich

On list-coloring extensions.

A classical Brooks theorem states that any graph (which is not complete or an odd cycle) with maximum degree D can be colored in at most D colors so that any two adjacent vertices get different colors.

Coloring extension problem is concerned with finding the smallest number of colors needed to color the vertices of a graph if some subset of vertices is precolored. We shall discuss some color extension results when the distance constraint is given for the precolored vertices. These results will include the D-list-coloring of general graphs and the 5-list-coloring of planar graphs.

Mar 17

NO SEMINAR-SPRING BREAK

Mar 24

Luke Paben

Edge-Colorings of Simple, Complete Graphs which Forbid "Rainbow" Cycles

Let K(n) denote a simple, complete graph of size n. It is possible to show that colorings that forbid "rainbow" triangles (that is, all edges in the triangle have a different color) also forbid rainbow cycles. These colorings have some interesting structural properties that will be investigated in the talk. This talk should be accessible to everyone with a basic understanding of graph theory.

Mar 31

Ryan Martin*

On Avoider-Enforcer games

Positional games are two-player games in which both players have perfect information and alternately choose elements from a set. In the Avoider-Enforcer game on the complete graph $K_n$, the players (Avoider and Enforcer) each take one edge in turn. Given a graph property $P$, Enforcer wins the game if Avoider's graph has the property $P$. An important parameter is $\tau_E(P)$, the smallest integer $t$ such that Enforcer can win the game against any opponent in $t$ rounds. In this talk, let $F$ be an arbitrary family of graphs and $P$ be the property that a member of $F$ is a subgraph or is an induced subgraph. We determine the asymptotic value of $\tau_E(P)$ when $F$ contains no bipartite graph and establish that $\tau_E(P) = o(n^2)$ if $F$ contains a bipartite graph.
The proof uses the game of JumbleG and Szemeredi's regularity lemma.
Joint work with Jozsef Balogh, UIUC.

Apr 07

Laura DeLoss

Determining minimum skew rank of matrices described by a graph: results using cut-vertex reduction on coronas

Apr 14

Ryan Martin

Apr 21

Jason Grout

Ultraconnected graphs and partial matrix completion problems.

Given a matrix with only some entries filled in (in a symmetric way) and a property $P$, we ask if we can fill in the rest of the entries so that the filled-in matrix has property $P$. For certain properties $P$, including positive definite and the property that the matrix is a Euclidean distance matrix, the patterns that allow completions are connected with a structural property we call ultraconnectedness. I will give some background on this problem and discuss a variety of results about ultraconnected graphs.

Apr 28

JiHyeok Choi

Anti-Ramsey number for cycles

Date

Name

Title

Abstract

Aug 26

Organizational Meeting

Sep 2

Olga Pryporova

Sep 9

Canceled in favor of Benny Sudakov's colloquium talk

Sep 16

Jake Manske

Sunshine, Lollipops, and Rainbow Subposets of the Boolean Lattice

Sep 23

Jake Manske

It's my poset and I'll cry if I want to

Sep 30

Jason Smith

Conjunctive Normal Form and Its Representational Power

The talk will introduce the Satisfiability Problem and subsequently its Conjunctive Normal Form. A hierarchy will be established for the 'representational power' of conjunctive normal form. Then there may be some discussion of closure properties, some examples of empirical data, and a lot of discussion of what could still possibly be done.

Oct 7

Maria Axenovich

On voting games and 3-chromatic hypergraphs

A simple voting game is a set of winning coalitions in a voting scheme, i.e., it is a family of non-empty subsets of an n-element set closed under taking supersets. A simple voting game thus corresponds to a filter in a boolean lattice. We investigate the properties of maximal voting games and dependencies of the number of winning coalitions on the structure of minimal winning coalitions. This is a joint work with Sonali Roy.

Oct 14

Jeremy Alm

The logical roots of Ramsey's theorem

Oct 21

Ji-Hyeok Choi

Some mixed anti-Ramsey numbers on cycles

Oct 28

Tracy McKay

W. G. Brown's Construction for Graphs That Do Not Contain a Thomsen Graph

Nov 4

Ryan Martin

The expander mixing lemma

Nov 11

Luz DeAlba

Minimum Skew Rank and the diameter of a graph.

In this talk we take a look at some graphs, G, for which the minimum skew rank of G equals the diameter of G. We also extend our studies to include some graphs, H, for which the minimum skew rank of H equal the minimum skew rank of the longest induced path in H.

Nov 18

Rana Mikkelson

Nov 25

Canceled for Thanksgiving Break

Dec 2

Jason Grout

The minimum rank problem for powers of graphs.

Dec 9

Michelle Lastrina

Date

Name

Title

Abstract

Jan 15

Organizational Meeting

Jan 22

Luz De Alba

Matrix Completion Problems

Jan 29

Luz De Alba

The Q-matrix Completion Problems

Overhead Notes

Feb 5

Maria Axenovich

On transversals of longest paths in graphs.

It is an easy fact that any two longest paths in a connected graph share a vertex. It is more difficult to prove that there are graphs in which several (at least 7) longest paths do not share a common vertex. The following question remains open now for several decades. Is it true that any three longest paths in a connected graph share a vertex? We shall discuss several results related to this question.

Feb 12

Jack Lutz

Combinatorial Aspects of Nanoscale Self-Assembly

DNA tile self-assembly, pioneered by Seeman in the 1980s, is a promising approach to engineering structures that autonomously assemble themselves from molecular components. These structures, which may be complex and aperiodic, can be programmed, in the sense that they are determined by a designer's selection of the finite set of molecular component (DNA tile) types from which the structures self- assemble.

The Tile Assembly Model, introduced by Winfree in the late 1990s, is a mathematical model of DNA tile self-assembly. Winfree showed that discrete Sierpinski triangles can self- assemble in the Tile Assembly Model, and a striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic- force microscopy, was achieved by Rothemund, Papadakis, and Winfree in 2004.

Winfree also proved that any computer program (Turing machine) can be translated into a finite set of tile types whose self-assembly executes that program. The collection of structures that can be programmed to self-assemble is thus very rich.

In this talk I will survey these developments, along with some recent work in which Jim Lathrop, Matt Patitz, Scott Summers, and I have explored the theoretical power and limitations of tile self-assembly. I will also discuss the need for new combinatorial arguments to further this exploration.

Feb 19

Ryan Martin

The Vertex Ramsey Problem.

Feb 26

Jason Grout

Mar 4

Jake Manske

Monochromatic subsets of the integer grid

For an integer n, let [n] denote the integer set {0, 1, ..., n-1}. For any subset V of Z x Z, let Hom(V) = {cV + b : c a positive integer, b an element of Z x Z}. For any positive integer k, let Rk(V) denote the least integer N such that for any n > N and for any k-coloring of [N] x [N], there is a monochromatic subset U from Hom(V). The argument of Gallai ensures that Rk(V) is finite. We investigate bounds on Rk(V) when V is a three or four-point configuration in general position.

Mar 11

No seminar in favor of the colloquium by Hemanshu Kaul on Friday, Mar. 7, Carver 202, 3:10p.m.-4p.m.

See the Colloquium schedule for Hemanshu's title and abstract.

Mar 18

Spring Break; No seminar.

Mar 25

Apr 1

Leslie Hogben

Minimum Rank of Not Necessarily Symmetric Matrix Patterns

Apr 8

Rana Mikkelson and Kaela Rasmussen

Universally optimal matrices and field independence of the minimum rank of a graph

Apr 15

Tracy McKay, Jason Smith

Software for computation of Minimum Rank

Apr 22

Laura DeLoss, Geoff Tims

The Graph Complement Conjecture for Minimum Rank

Apr 29

Olga Pryporova

Diagonal and D-convergence of matrices

Aug. 21

Welcome and organizational meeting

Aug. 28

Jason Grout

The minimum rank problem over finite fields:
or "Yet another problem that projective geometry answers!"

Sept. 4

Sept. 11

Alex Roitershtein

Random strategies for the Robin Hood game

Sept. 18

Leslie Hogben

Minimum rank of nonsymmetric matrices described by a digraph

Sept. 25

 Th Sept. 27, 3:40pm,
DCS Lecture
101 Carver

F.R. (Buck) McMorris,
Illinois Institute of Technology

Majority-rule consensus: from preferences
(social choice) to trees (biology)

Oct. 2

Ryan Martin

Edit distance in graphs: Colored regularity graphs

T Oct. 2: 4:10pm,
Colloquium
150 Carver

Leif Jorgensen,
Aalborg University, Denmark

Directed strongly regular graphs

Oct. 9

Colloquium replaces seminar

T Oct. 9: 4:10pm,
Colloquium
150 Carver

Chris Godsil,
U. of  Waterloo

Association schemes and type-II matrices

Th Oct. 11: 3:30pm,
Miller Lecture
Auditorium, Howe Hall

Daniel Gusfield,
U. of California, Davis

ReCombinatorics: Combinatorial Algorithms for Studying The History of Recombination in Populations

Oct. 16

Chad Brewbaker

An Introduction to Computational Genetics for the Graph Theorist

Oct. 23

Olga Pryporova

Qualitative Convergence of Matrices

Oct. 30

Leslie Hogben

Teaching Linear Algebra: Technology and Resources

Nov. 6

Seminar replaced by First Year Seminar on Wednesday 4:10pm

W Nov 7: 4:10pm,
Seminar for First year Mathematics Graduate Students

Leslie Hogben

Minimum Rank Problems and the Early Graduate Research seminar for Spring 08

Nov. 13

Seminar replaced by First Year Seminar on Wednesday 4:10pm

W Nov 14: 4:10pm,
Seminar for First year Mathematics Graduate Students

Ryan Martin

The edit distance in graphs

Nov. 20

VACATION

Nov. 27

Rana Mikkelson

Minimum rank of graphs with loops

Dec. 4

Ryan Martin

Forbidden subgraphs of Unit Disk Graphs