ISU DISCRETE MATHEMATICS SEMINAR
Time: Tuesdays 2:10-3:00 Place: 401 Carver (seminar room)
WORKING SEMINAR: TUESDAYS 1:10-2:00
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 faculty and graduate students who are not specialists in the area.
or to volunteer to speak in the seminar, please contact
Ryan Martin (rymartin AT iastate DOT edu) or Leslie Hogben (lhogben AT iastate DOT edu)
|Date||Speaker||Title (abstract is linked)|
|Aug 27||Organizational Meeting|
|Sep 03||NO SEMINAR, second hour of working seminar|
F, Sep 06
||Honors Salon: Steve Butler||The mathematics of juggling|
|Su, Sep 08||Math Club/Pi Mu Epsilon (ΠΜΕ): Steve Butler||The 291 decillion ways to tile with Tetris|
|Sep 10||Steve Butler||Permutations which avoid the patterns 1324 and 2(14)3|
|R, Oct 15||Computer Science Department colloquium: Derrick Stolee||Computational combinatorics and the search for uniquely Kr-saturated graphs|
|Sep 17||Michael Young||The anti-Ramsey number of a matching|
|Sep 24||Derrick Stolee||On independent sets in Cayley graphs over Z|
|Oct 01||James Carraher, University of Nebraska-Lincoln||Compatible circuits in colored eulerian digraphs|
||MECS Interdisciplinary Seminar: Leslie Hogben||Minimum rank problems|
|Oct 08||C. H. Lin||Counterexamples to an edge spread question for zero forcing number|
|Oct 15||Minnie Catral, Xavier University||Principal rank characteristic sequences|
||Colloquium: Ryan Martin||The edit distance in graphs|
||Colloquium replaces seminar: Mike Ferrara, University of Colorado-Denver||Realization problems for degree sequences|
|M, Oct 28||
James Ostrowski, University of Tennessee-Knoxville
|Symmetry in integer programming|
|Oct 29||James Ostrowski, University of Tennessee-Knoxville||Constraint orbital branching|
|Nov 05||Cathy Erbes, University of Colorado-Denver||Extremal problems for degree sequences|
|Nov 12||Nicole Kingsley||Propagation time for skew-symmetric zero forcing|
|Nov 19||Nathan Warnberg||Positive semidefinite migration|
|Nov 25-29: Thanksgiving Break, No Seminar|
M Dec 02
|Dec 03||Ryan Martin||On matrices and quadratic programs|
M Dec 09
|Dec 10||Lucas Kramer|
Dec 03: Ryan Martin, On matrices and quadratic programs. I will discuss the method of symmetrization, originated by Sidorenko and used to compute edit distance functions.
Nov 19: Nathan Warnberg, Positive semidefinite migration. Imagine that you would like to start a rumor so that eventually everyone in your school is aware of the rumor. To accomplish this you need to come up with a model for the relationships that exist in the population and how the rumor is spread from person to person. Let G be a graph whose vertices are people and whose edges represent a `friendship.' Represent the people that know the rumor by coloring their corresponding vertex blue and represent the people that don't know the rumor by leaving their vertex white. There are several rules for how the rumor can be transmitted and we will discuss one such rule, namely the positive semidefinite (PSD) color change rule. The PSD color change rule (rumor spreading rule) is as follows: Let B be the initial set of blue vertices and W1,W2,...,Wk be the connected components of the graph G without the blue vertices B. Reattach the blue vertices to connected component Wi to get the induced subgraph G[WiÈB]. In G[WiÈB] we say that a blue vertex bÎB can force a white vertex wÎWi to be color blue (b tells w the rumor) if w is the only white neighbor of b. If we can color the entire graph blue (spread the rumor to the entire population) using this rule iteratively then we say B is a positive semidefinite zero forcing set (PSDZFS). The size of the smallest such set is the positive semidefinite zero forcing number. The number of iterations of our color change rule needed to force the entire graph blue is called the positive semidefinite propagation time. We will examine the ability to move from one minimum PSDZFS to another and how this affects the PSD propagation time.
Nov 05: Catherine Erbes, University of Colorado-Denver, Extremal problems for degree sequences. A sequence of nonnegative integers is graphic if it is the degree sequence of a graph G. Given a graph H, a graphic sequence π is potentially H-graphic if there is a graph G with degree sequence π such that G contains H as a subgraph. The potential number of a graph H, denoted σ(H,n), is the minimum even integer such that any graphic sequence of length n and sum at least σ(H,n) is potentially H-graphic. This is the degree-sequence analogue of the classical extremal number. The potential number has been determined asymptotically for general graphs H, and a family of extremal sequences that achieve this number is known.
In this talk we discuss two results about graphic sequences that are not potentially H-graphic. The first concerns the structure of such sequences, and shows that this structure is close to that of the extremal sequences. The second is a stability result for the potential problem, similar to the stability results of Erdős and Simonovits for the Turán problem. We say that a graph H has degree-sequence stability if every graphic sequence with sum close to σ(H,n) that is not potentially H-graphic can be transformed into an extremal sequence with o(n) additions and subtractions. We discuss families of graphs that do and do not have degree-sequence stability.
Oct 29: James Ostrowski, University of Tennessee-Knoxville, Constraint orbital branching. Orbital branching is a method for branching on variables in integer programming that reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branching methodology is extended so that the branching disjunction can be based on an arbitrary constraint. Many important families of integer programs are structured such that small instances from the family are embedded in larger instances. This structural information can be exploited to define a group of strong constraints on which to base the orbital branching disjunction. The symmetric nature of the problems is further exploited by enumerating non-isomorphic solutions to instances of the small family and using these solutions to create a collection of typically easy-to-solve integer programs. The solution of each integer program in the collection is equivalent to solving the original large instance. The effectiveness of this methodology is demonstrated by computing the optimal incidence width of Steiner Triple Systems and minimum cardinality covering designs.
Oct 08: C. H. Lin, Counterexamples to an edge spread question for zero forcing number. The edge spread of a graph G on an edge e is defined as Z(G)-Z(G-e), where Z(G) is the zero forcing number of G. Edholm et al. showed that an edge is contained in all maximal chain if the edge spread is -1, and asked whether the converse is true or not. We gave a negative answer to this question by constructing a family of counterexamples.
Oct 01: James Carraher, University of Nebraska-Lincoln, Compatible circuits in colored eulerian digraphs. Let G be an edge-colored eulerian digraph (not necessarily properly edge-colored). A compatible circuit is an eulerian circuit T of G such that T has no monochromatic transitions. We characterize the existence of a compatible circuit when G does not contain any vertices of outdegree three. This result is a strenghening of results by Fleischner and Isaak. We discuss the complications when G contains vertices of outdegree three. We investigate when 3-regular colored eulerian digraphs have a compatible circuit.
Sep 24: Derrick Stolee, On independent sets in Cayley graphs over Z. A circulant graph is a Cayley graph over Zn Determing the independence number or clique number of a circulant graph is a difficult problem. Motivated by recent work on uniquely Kr-saturated graphs, we investigate the density of independent sets in finitely-generated Cayley graphs over the integers. We use a search for periodic sets to provide lower bounds and use discharging arguments to find upper bounds. We are able to determine the exact density for many generator sets, but also state several conjectures. This is joint work with James Carraher, David Galvin, Stephen G. Hartke, and A. J. Radcliffe.
Sep 10: Steve Butler, Permutations which avoid the patterns 1324 and 2(14)3. Given a permutation of [n], call it p, we can construct a graph Gp on the vertices [n] where there is an edge between i and j if and only if i<j, p(i)<p(j), and there is no k satisfying i<k<j and p(i)<p(k)<p(j). We show that the permutations whose graphs are forests are characterized in terms of avoidance of two patterns.
Selected conferences in 2013-2014:
Jan 15-18, 2014: Joint Mathematics Meetings in Baltimore, MD. [Funding for graduate students available.]
Mar 06-08, 2014: NIMBioS workshop on Animal Social Networks. [Prof. Martin attending, application due date December 02, 2014.]
Mar 15-16, 2014: 1st Lake Michigan Workshop on Combinatorics and Graph Theory [Accommodation for students is likely to be funded, contact Dr. Martin if interested.]
Mar 19-21, 2014: Possible meeting on Identifying Codes at Morehead State in Morehead, KY. [Prof. Martin scheduled to speak.]
Mar 10-Jun 13, 2014: IPAM Program on Algebraic Techniques for Combinatorial and Computational Geometry. [Request for financial support due December 10, 2013.]
Mar 24-28: Workshop I: Combinatorial Geometry Problems at the Algebraic Interface [Request for financial support due January 27, 2014.]
Apr 07-11: Workshop II: Tools from Algebraic Geometry [Request for financial support due February 10, 2014.]
May 05-09: Workshop III: The Kakeya problem, Restriction problem, and Sum-product Theory [Request for financial support due March 03, 2014.]
May 19-23: Workshop IV: Finding Algebraic Structures in Extremal Combinatorial Configurations [Request for financial support due March 24, 2014.]
June 16-19, 2014: SIAM DM14: Hyatt Regency hotel, Minneapolis, MN. [SIAM student travel awards available, usually one per adviser. Deadline in Nov/Dec. 2013.]
June 29-July 03, 2014: International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC) in Chicago, IL.
Fall 2014-Spring 2015: IMA Thematic Year on Discrete Structures, Minneapolis, MN.
Sep 08-12, 2014: Workshop: Probabilistic and Extremal Combinatorics
Sep 29-Oct 03, 2014: Workshop: Additive and Analytic Combinatorics
Nov 10-14, 2014: Workshop: Geometric and Enumerative Combinatorics
Feb 23-27, 2015: Workshop: Convexity and Optimization: Theory and Applications
Mar 16-20, 2015: Workshop: Determinism versus Randomization in Computation (offsite at Georgia Tech)
Apr 13-17, 2015: Workshop: Information Theory and Concentration Phenomenon
May 18-22, 2015: Workshop: Graphical Models, Statistical Interference, and Algorithms (GRAMSIA)
Jun 22-26, 2015: Workshop: Analytical tools in Probability and Applications (offsite at the Euler Institute, St. Petersburg, Russia)
|Date||Speaker||Title (abstract is linked)|
|Jan 14||NO SEMINAR|
|Jan 21||Organizational Meeting|
|Feb 25||Paul Wenger, Rochester Institute of Technology|
|Mar 18-22 Spring Break, No Seminar|
|Apr 08||Richard Mycroft, University of Birmingham, UK|
Discrete Math Seminar. Updated by Ryan Martin: 12 November 2013