ISU DISCRETE MATHEMATICS SEMINAR
2007-2008

Time: Tuesdays 1:10 PM       Place: 294 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 08 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.