Combinatorics Abstracts

On a class of selfdual ternary codes

Krishnasamy T. Arasu

In this joint work with YuQing Chen, Aaron Gulliver and Weilai Song, we investigate certain construction methods for selfdual ternary codes using a class of conference matrices. The equivalence between our codes and those of Pless (symmetry codes) is also established.

DEPT OF MATH & STAT
WRIGHT STATE UNIVERSITY
DAYTON, OH 45435
karasu at math.wright.edu

+++++++++++++++++++++++++++++++++++++++

Steiner 3-designs: Results Old and New

Niranjan Balachandran

While the theory of block designs (2-designs) has culminated in a lot of interesting results and techniques (both algebraic and combinatorial), the theory of 3-designs, more specifically, Steiner 3-designs, is far from satisfactory. In this talk, we shall first survey some of the known results regarding Steiner 3-designs and look at some of the techniques in the context of 2-designs and their counterparts for the case t=3. We shall also consider other set systems with distinctive structures(Candelabra Set Systems and Rooted Forest Set Systems) and their relations with Steiner 3-designs to get a grasp on this problem.

DEPARTMENT OF MATHEMATICS
THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
niranj at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

Cyclic Flats and Transversal Matroids

Joseph Edmond Bonin

A cyclic flat in a matroid is a flat that is a union of circuits. The cyclic flats of a matroid, ordered by inclusion, form a lattice; indeed, every lattice can be obtained, up to isomorphism, as the lattice of cyclic flats of some matroid.

A matroid is determined by its cyclic flats and their ranks, but not by the cyclic flats alone. A transversal matroid and a non-transversal matroid may have the same cyclic flats. The focus of this talk is the exception: under special order-theoretic hypotheses, all matroids with a given lattice of cyclic flats are transversal.

THE GEORGE WASHINGTON UNIVERSITY
1922 F STREET
WASHINGTON, DC 20052
jbonin at gwu.edu

+++++++++++++++++++++++++++++++++++++++

Latin squares, orthogonal mates, and groups

Anthony Brian Evans

Given a latin square, Does it have an orthogonal mate? We will discuss answers to this question when L is the multiplication table of a group or has a group-like structure.

WRIGHT STATE UNIVERSITY
DAYTON, OH 45435
anthony.evans at wright.edu

+++++++++++++++++++++++++++++++++++++++

Minimal non-orientable matroids in a projective plane

Rigoberto Florez

We construct a family of minimal non-orientable matroid of rank three. Some of these matroids are embeded in Desarguesian projective planes. This answer a question of Ziegler: For every prime power of q, find a minimal non-orientable submatroid of the projective plane over the q-elements field.

UNIVERSITY OF SOUTH CAROLINA SUMTER
200 MILLER RD.
SUMTER, SOUTH CAROLINA
florezr at uscsumter.edu

+++++++++++++++++++++++++++++++++++++++

Excluding a group-labelled graph

Jim Geelen

We prove a structure theorem on group-labelled graphs (or biased graphs) that, together with the graph minors structure theorem of Robertson and Seymour, describes minor closed classes of group-labelled graphs over finite abelian groups. This implies structural results on the class of Dowling matroids.

This is joint work with Bert Gerards and Paul Seymour.

UNIVERSITY OF WATERLOO
WATERLOO, CANADA
jfgeelen at uwaterloo.ca

+++++++++++++++++++++++++++++++++++++++

Zeros for Rook Polynomials

Jim B. Haglund

We discuss a conjecture of Ono, Wagner and the speaker on the zeros of a certain pernament with many parameters, and how it relates to the zeros of rook and matching polynomials.

DEPARTMENT OF MATHEMATICS
THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
jhaglund at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

Routing sets in the integer lattice

Peter Hamburger

A set of vertices S in a graph G is a routing if it ensures connectivity between all pairs of vertices outside of s. Additional constraints may apply; a connected dominating set, for instance, is a special case of a routing set. We determine the size of a minimum routing network in subgraphs of the integer lattice, as well as (asymptotically) for the lattice itself.

This is joint work with Robert Vandell, and Matt Walsh, IPFW.

IPFW
FORT WAYNE, IN 46805
hamburge at ipfw.edu

+++++++++++++++++++++++++++++++++++++++

Evolutionary Game Theory and the Iterated Prisoner's Dilemma

Douglas G. Kelly

We introduce the Iterated Prisoner's Dilemma (IPD) and the “replicator dynamics†equations for the ecology of a given set of strategies for the IPD. We describe the connections between game-theoretic properties such as Nash equilibrium and evolutionary stability on the one hand, and dynamic properties such as Lyapunov stability on the other. We illustrate with the analysis of a particular subclass of three-strategy populations, motivated by a surprising example showing that the well-known ''Tit for Tat'' strategy is not always evolutionarily stable.

UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL
CHAPEL HILL, NC 27519-3260
dgkelly at email.unc.edu

+++++++++++++++++++++++++++++++++++++++

Graphs with restricted valecy and matching numbers

Niraj Khare

Consider the family of all finite graphs with maximum degree less than d and maximum matching size less than m. We find the precise upper bound, $e(d,m)$ for the number of edges in such graphs. We also find a lower bound for the maximum matching size of a graph $G$ with $\vert E(G)\vert > e(d,m)$ and $\Delta (G) < d$ .

THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
nirajkhare at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

(missing)

Bogdan Oporowski

(missing)

DEPARTMENT OF MATHEMATICS
LOUISIANA STATE UNIVERSITY
BATON ROUGE, LA 70803
bogdan at math.lsu.edu

+++++++++++++++++++++++++++++++++++++++

Towards a Grid Theorem for Rank-width and Clique-width (joint work with J. Geelen)

Sang-Il Oum

Robertson and Seymour proved that if a graph G does not contain a fixed planar graph, then treewidth of G is bounded. This theorem has been generalized to binary matroids by Geelen, Gerards, and Whittle. It would be interesting to know whether there is an analogous theorem to rank-width (equivalently, to clique-width). A conjecture is that if a graph G does not contain a fixed bipartite circle graph as a pivot-minor, then rank-width of G is bounded. Interestingly this conjecture would, if it is true, imply the previous two theorems. We survey the known special cases of this conjecture and discuss the new result (joint work with Jim Geelen).

SCHOOL OF MATHEMATICS
GEORGIA INSTITUTE OF TECHNOLOGY
686 CHERRY ST
ATLANTA, GA 30318
add math.gatech.edu to sangil@

+++++++++++++++++++++++++++++++++++++++

(Missing)

James Oxley

(Missing)

(MISSING)
(MISSING)
(MISSING)
(MISSING)
(Missing)

+++++++++++++++++++++++++++++++++++++++

(Bell and Stirling Numbers for Graphs)

Rhodes Peele

A partition $P$ of the vertex set $V$ of a graph $G = (V,E)$ is called $G$ -admissible if, for all $(x,y)$ in $E$ , vertices $x$ and $y$ are in different blocks of $P$ . In this talk, we call the number of $G$ -admissible partitions, the Bell number of the graph $G$ ; this numerical invariant of $G$ will be denoted $B(G)$ . (For the empty graph $En$ we have $B(En) = Bn$ , the classical Bell number.) Similarly, $S(G,k)$ will denote the number of $G$ -admissible partitions of $G$ with exactly $k$ blocks; we think of it as a generalized Stirling number of the Second Kind.

This talk grew out of my supervision of an undergraduate independent study for Mr. Bryce Duncan, a senior at Auburn University Montgomery. Mr. Duncan wanted to know the value of $B(Pn)$ for the path consisting of edges $(1,2)$ , $(2,3)$ , ... , $(n-1,n)$ . To our surprise it turned out to be $Bn-1$ .

We discuss several strategies for calculating B(G). These include:

1. bijective correspondences;
2. deletion and contraction (although $B(G)$ is not a simple evaluation of the Tutte polynomial of $G$ );
3. linear recurrences.

MATH DEPT.
AUBURN UNIVERSITY MONTGOMERY
P.O. BOX 244023
MONTGOMERY, AL 36124
peelhor at mindspring.com

+++++++++++++++++++++++++++++++++++++++

Conjectures on Circuits and Clones in Matroids

Talmage James Reid

Scott Smith conjectured in 1979 that two distinct longest cycles of a $k$ -connected graph meet in at least $k$ vertices when $k \geq 2$ . This conjecture is known to be true for $k \leq 10$ . Extensions of this conjecture to matroids are considered. A conjecture that relates Smith's Conjecture to results of Sean McGuinness on cycle pairs of a graph that are of smaller size than the circumference of the graph is given.

Elements $e$ and $f$ in a matroid $M$ are clones if interchanging $e$ and $f$ and fixing all other elements is an automorphism of $M$ . We investigate the number of clones that a matroid that is representable over a small field may have as well as the relationship between clones and specified minors in a matroid.

The circuit conjectures and results are the result of joint work with Lemos, McGuinness, McMurray, Sheppardson, Williams, Wei, and Wu. The conjectures and results on clones in matroids are the result of joint work with Bonin, Cotwright, and Robbins.

THE UNIVERSITY OF MISSISSIPPI
300 MURRAY ST
OXFORD, MS 38655
mmreid at olemiss.edu

+++++++++++++++++++++++++++++++++++++++

Towards a Converse to Cook's Theorem in Complexity Theory

Neil Robertson

Cook's theorem says that the class of NP-problems is dominated, up to polynomial-time equivalence, by the problem of testing satisfiability of logical propositions. If satisfiability is not itself polynomial-time testible, it is known that there are countably many problems, up to polynomial equivalence, which do not dominate NP. A converse to Cook's theorem would describe concretely these intermediate problems (enough to dominate all such problems) and from them prove satisfiability can be recovered in a uniformly polynomially bounded fashion which would show that the class does indeed dominate all intermediate problems. Such a theorem would describe the class of NP-problems in a concrete way without directly settling the basic P=NP problem. Some thoughts on how to begin to go about this process, which is easier said than done, will be given in this lecture.

THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
robertso at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

Regular signed-graphic matroids

Daniel C. Slilaty

Except for a few trivial cases, the matroid of a signed graph is a regular matroid iff the signed graph has no two vertex-disjoint negative cycles.

If a graph is imbedded in the real projective plane, then there is a signing on the edges such that a cycle is negative iff it is imbedded as a noncontractible closed curve. A signed graph obtained in this fashion is called a projective-planar signed graph.

It is a topological fact that two noncontractible closed curves on the projective plane must intersect. Thus a projective-planar signed graph cannot have two vertex-disjoint negative cycles. Conversely, suppose that S is a signed graph without two vertex-disjoint negative cycles. In this talk we will discuss how S may be constructed from a projective-planar signed graph except for some trivial cases.

WRIGHT STATE UNIVERSITY
DAYTON, OH 45432
daniel.slilaty at wright.edu

+++++++++++++++++++++++++++++++++++++++

Generalizations of Selberg's Integral

Laura Jeanne Stevens

In 1944, A. Selberg proved a remarkable formula generalizing Euler's formula for the Beta function as a quotient of Gamma functions. In recent years, a number of generalizations of Selberg's integral have been discovered. I will discuss a few of these, some of which are related to exciting breakthroughs in algebraic combinatorics.

DEPARTMENT OF MATHEMATICS
THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
stevens at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

Identities between Thompson Series and Rogers-Ramanujan Functions

Holly Marie Swisher

At one point in his life, Ramanujan listed $40$ identities involving what are now called the Rogers-Ramanujan functions $G(q)$ and $H(q)$ on one side, and products of functions of the form $Q_m = \prod_{n=1}^\infty (1-q^{mn})$ on the other side. The identities are rather complicated and seem too difficult to guess. Recently however, Koike devised a strategy for finding (but not proving) these types of identities by connecting them to Thompson series. He was able to conjecture many new Rogers-Ramanujan type identities between $G(q)$ and $H(q)$ , and Thompson series. Here we prove these identities.

DEPARTMENT OF MATHEMATICS
THE OHIO STATE UNIVERSITY
COLUMBUS, OH 43210
swisher at math.ohio-state.edu

+++++++++++++++++++++++++++++++++++++++

Columns of Uniform Color in a Cyclically Repeated Pattern of 3 Colors

Steve Szabo

The purpose of this talk is to study the following problem: consider coprime positive integers $p_1$ ,...., $p_n$ and a rectangular array of balls of $m$ different colors with the $i$ th row containing $p_i$ balls of each color cyclically repeated. The problem is to find the number of columns having balls of same color. This problem is of great importance in Molecular biology. Nagpaul-Jain gave the complete solution of the question in the $m=2$ case. For $m>2$ they only studied restricted cases where all rows start with same color and all $p_i$ are congruent to one another modulo $m$ . We give the complete solution to the problem for $m=3$ without assuming any additional conditions.

This is a joint work with Ashish K. Srivastava.

OHIO UNIVERSITY
ATHENS, OH 45701
szabo at math.ohiou.edu

+++++++++++++++++++++++++++++++++++++++

Matroids and Coxeter Matroids

Neil White

Coxeter matroids are a generalization of matroids, based on a finite Coxeter group. This talk will introduce Coxeter matroids, and concentrate on flag matroids, which are the special case of Coxeter matroids most closely related to (ordinary) matroids. We include some results on ordinary matroids which were first obtained by this approach. this talk will be suitable for graduate students with a background in elementary matroid theory and a beginning graduate course in group theory.

MATH DEPT.
UNIVERSITY OF FLORIDA
P.O.BOX 118105
GAINESVILLE, FL 32611-8105
white at math.ufl.edu

+++++++++++++++++++++++++++++++++++++++

A symplectic Hamada's formula

Qing Xiang

Let $V$ be a $2m$ -dimensional vector space over ${\rm GF}(q)$ , where $q=p^t$ , $p$ a prime. We equip V with a nonsingular alternating form. Let ${\mathcal I}_r$ denote the set of totally isotropic $r$ -dimensional subspaces of $V$ with respect to the alternating form, where $1\leq r\leq m$ . The symplectic polar space ${\rm Sp}(2m,q)$ is the geometry with flats ${\mathcal I}_r$ , $1\leq r\leq m$ . We derive an additive formula for the $p$ -rank of the incidence matrix between 1-flats and $r$ -flats of ${\rm Sp}(2m,q)$ . This is the symplectic analogue of Hamada's formula for the $p$ -rank of the incidence matrix between 1-dimensional subspaces and $r$ -dimensional subspaces of $V$ .

UNIVERSITY OF DELAWARE
NEWARK, DE 19716
xiang at math.udel.edu

+++++++++++++++++++++++++++++++++++++++

A Complicated Tutte Invariant

Thomas Zaslavsky

A problem of counting lattice points led David Forge and me to discover an intriguing polynomial function of rooted integral gain graphs - graphs where each edge is labelled invertibly by an integer, and there is a special "root" vertex. The polynomial satisfies the standard deletion-contraction law and a multiplicative law and is preserved by isomorphism; i.e., it is a Tutte invariant, and thus analogous to the ordinary Tutte polynomial of a graph or matroid. However, our polynomial has the unusual feature that it is a function of infinitely many variables, whereas ordinary Tutte polynomials have only two variables. A similar infinitude appears in the polynomial of Noble and Welsh (1999) and there is a common partial generalization.

In our case, unlike that of Noble and Welsh, the polynomial is not a universal Tutte invariant, hence, it is not a true Tutte polynomial. The problem of finding the universal Tutte invariant is unsolved. Examples suggest that such a universal will be more complicated than a polynomial; it may require new algebra.

DEPT. OF MATHEMATICAL SCIENCES
BINGHAMTON UNIVERSITY (SUNY)
BINGHAMTON, NY 13902-6000
zaslav at math.binghamton.edu