ISU DISCRETE MATHEMATICS SEMINAR
2008-2009

Time: Tuesdays 2:10 PM       Place: 174 Carver

The Discrete Mathematics Seminar at Iowa State University is an eclectic mix of topics, including graph theory, combinatorics, linear algebra and abstract algebra. Presentations vary with the speaker and include the speaker's research, related research by others, and expository talks. Many of the expository talks (typically labeled as "Introduction to") are suitable for interested graduate students and faculty who are not specialists in the area.

For questions or to volunteer to speak in the seminar, please contact Jason Grout or Ryan Martin


Spring 2009 Seminars

A * following the name means that the talk is a technology talk and will use a computer projector.

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


Salah Aly completed his Ph.D. in Computer Science at Texas A&M University. He worked in a research internship at Bell-Labs & Alcatel-Lucent in NJ. He is currently a research associate at Iowa State University. His research areas include classical and quantum information processing particularly in the areas of error control codes, algorithms, network coding and information security including their applications in wireless networks and storage systems.

Fall 2008 Seminars

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





Spring 2008 Seminars

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


Upcoming Conferences:


Fall 07 Seminars     

Time: Tuesdays 2:10 PM        Place: 074 Carver

Date

Name

Title

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

Oct. 9: Chris Godsil: Association schemes and type-II matrices

Type-II matrices are a class of matrices that were used by Vaughan Jones to construct interesting new invariants of knots and links, known as spin models. They are closely related to a number of combinatorial objects, and in particular to association schemes. I this talk I will develop this connection, and discuss the open problems that result.

Oct. 16: Chad Brewbaker: An Introduction to Computational Genetics for the Graph Theorist

We will introduce the basic algorithms and biology needed for performing genome shotgun assembly . Also, we will review some basic properties of the scale free and sparse near-planar graphs that arise.
Due to the size of these data sets we are only able to recognize and exploit properties of the graph that can be computed in linear or O(E log(E)) time and space where E is the number of edges. Also, since the data sets are so large we must distribute the computations over many computers. We will discuss open challenges related to finding interesting properties of these graphs that can be computed in near-linear time, space, and communication.

Dec. 4: Ryan Martin: Forbidden subgraphs of Unit Disk Graphs

So-called unit disk graphs (UDGs) are graphs in which adjacency is determined by proximity. A finite number of vertices are put in the plane and they are adjacent if and only if they are of distance at most 1 from each other.

Computer scientists study UDGs because of their applications to wireless networks, although very little is known about the structure of UDGs.  I will present some very new results on UDGs as a result of joint work with Hemanshu Kaul of the Illinois Institute of Technology.  He will be visiting ISU in March.

The proof techniques involve basic geometry and the answer to the question "Why can't I draw a Venn diagram with 4 circles?"

Upcoming Conferences:


Archives: S07, F06, S06, F05, S05, F04, S04

Leslie Hogben's Home Page
Ryan Martin's Home Page

Discrete Math Seminar 2007-2008. Updated by Ryan Martin: 2007 Jun. 26.