Rocky Mountain Discrete Mathematics Days 2007

Rocky Mountain Discrete Mathematics Days
August 2-3, 2007
Colorado State University
Fort Collins, Colorado


Colorado State University will host the 10th annual Rocky Mountain Discrete Mathematics Days on August 2-3, 2007. The keynote speakers are
  1. Vera Pless (University of Illinois-Chicago): Self-dual and formally self-dual codes,
  2. Richard Green (University of Colorado): Some combinatorial aspects of simple Lie algebras,
  3. Qing Xiang (University of Delaware): Skew Hadamard difference sets from commutative semifields and symplectic spreads.


The goal of these annual meetings is to bring together students and researchers working in the broad area of Discrete Mathematics to discuss their recent work, and establish collaborations.


The conference will run from 1:00-6:00 on August 2nd, and from 9:00-6:00 on August 3rd. In addition to the talks by keynote speakers, there will be opportunities for contributed talks. Those wanting to give a contributed talk should submit a title and short abstract to Anton Betten (betten at math dot colostate dot edu) or Bryan Shader (bshader at uwyo dot edu) by July 22. Graduate students are encouraged to attend and to give presentations.


For those travelling longer distances, CSU has an arrangement with the Hilton Hotel. Contact information for the Hilton is:
425 W. Prospect Road, Fort Collins, Colorado, United States 80526 Tel: 1-970-482 2626 Fax: 1-970-493 6265
We have 10 rooms on hold until July 22 under the name of the local organizer at the rate $89/night + taxes. There is no confirmation number.


There is no registration fee for the conference. There is some funding available through an NSF and an NSA grant to help defray the local expenses of attendees. Priority for these funds is to graduate students, and minorities. If you would like to be considered for these funds, please send an e-mail with an estimate of your expenses (hotel, gas) to Bryan Shader by July 22.

Travel Information

This map displays travel information on how to get to the Hilton Hotel from I-25. Take exit Prospect Road and drive west for about 4 and a half miles. The Hilton is South of Prospect, opposite the CSU campus.


map2.png


Here a close-up view. The star marks the location of the Hilton Hotel (425 W. Prospect Rd). The gray area north of Prospect is the CSU Campus. The conference will take place in the vicinity of Weber Building, which is home the the Mathematics Department. Weber building is off oval drive, in exact westerly position (the green rectangle). Oval drive is in the North-East corner of the Campus. A walk from the Hilton Hotel takes around 10 minutes (the brown arrow in the picture).


map1b.png


The lecture hall reserved for the conference is Wagar 235. Wagar building is close to the math department. In the above map, you may be able to find the little appendix in the South-West corner of oval drive (the "nucleus"). Wagar building is South of there (the red dot). Parking is behind Weber building. If you need day passes, contact Anton Betten.


Here is a (Winter) photo of Weber building:
weber3.jpg

List of Speakers

At present, the following people have indicated that they would contribute a talk:
  1. Jeff Achter (Colorado State University),
  2. Anton Betten (Colorado State University),
  3. Bill Cherowitzo (University of Colorado at Denver and Health Sciences Center),
  4. Dan Daly (University of Denver),
  5. Jesse Gilbert (University of Colorado at Denver and Health Sciences Center),
  6. Soley Jonsdottir (Colorado State University),
  7. Oscar Jenkins (University of Colorado at Denver and Health Sciences Center),
  8. Cayla McBee (Colorado State University),
  9. Ross McConnell (Colorado State University),
  10. Eric Moorhouse (University of Wyoming),
  11. Stan Payne (University of Colorado at Denver and Health Sciences Center),
  12. Tim Penttila (Colorado State University),
  13. Rachel Pries (Colorado State University),
  14. Kyle Pula (University of Denver),
  15. Bryan Shader (University of Wyoming),
  16. Timothy Vis (University of Colorado at Denver and Health Sciences Center),
  17. Petr Vojtechovsky (University of Denver),

Abstracts of Invited Talks

Richard Green: Some combinatorial aspects of simple Lie algebras

I will discuss a combinatorial approach to the construction of almost all the simple Lie algebras over the complex numbers, with emphasis on the classical types (A, B, C and D). I will explain how the same construction, which can be thought of in terms of certain functions from partially ordered sets to graphs, can also be used to construct interesting permutation groups and polytopes. Familiarity with Lie algebras will not be assumed.

Vera Pless: Self-dual and formally self-dual codes

In the 70's there was much work on the classification of binary self-dual (s.d.) codes of modest length which culminated in 1980 in the classification of s.d. codes of length 32. Bounds are known for the largest minimum weight of Type I or Type II s.d. codes as their weight distributions satisfy the Gleason polynomials. The codes of largest minimum weight are called extremal codes and their weight distributions are uniquely determined. Vectors of a fixed weight in extremal codes hold designs. If the codes are Type 11 and extremal, which only exist at lengths divisible by 24, the designs are 5-designs. The Golay code is the unique extremal [24,12,8] code and there are five extremal [32,16,8] codes. There is a unique extremal [48,24,12] code.
A binary formally self-dual (f.s.d.) code is a code which has the same weight distribution as its dual code. They also satisfy the Gleason polynomials and hence the minimum weights of extremal codes are known as are their uniquely determined weight distributions. The extremal f.s.d. codes of lengths 10, 18 and 28 are unique. It is not known whether there is an extremal f.s.d. (or any) [40,20,10] code.
A f.s.d even code with d=2[n/8] is called near extremal. If C is a near extremal f.s.d. even code of length n with 8 dividing n, then its weight enumerator can be expressed in terms of one parameter which can only take on a finite number of values. For lengths 16, 24 and 32 some of these codes have been constructed. A few of the near extremal f.s.d codes are extremal s.d. codes.

Qing Xiang: Skew Hadamard difference sets from commutative semifields and symplectic spreads

Abstract

Abstracts of Contributed Talks

Jeff Achter: Counting, curves and classical groups

Given a finite field F, randomly chosen coefficients a and b in F, and a prime l, what is the chance that l divides the number of pairs (x,y) in F ×F such that
y2 = x3 + ax + b?
The answer to this question is encoded in the combinatorics of GL[2](Z/l).
More generally, many questions about curves over finite fields can be re-phrased as enumerative questions about classical groups. I'll sketch some recent results on classical groups, especially the symplectic group, and interpret this work in the context of curves.

Anton Betten: Some remarks on optimal codes

When is a code useful? Certainly, the information rate should be high, and the error correction capabilities should be good. But the complexity of encoding and decoding plays a role as well. Optimal linear codes maximize the minimum distance given the length and dimension and the size of the defining field (and have been studied for quite some time).
In this talk, we discuss two families of optimal linear codes which have the additional property that they are invariant under large automorphism groups (which may be used do devise efficient decoding algorithms).
The two types of codes are obtained by tensor twisting an oval in the plane with respect to a quadratic subfield, and by tensor twisting the projective line with respect to a cubic subfield (respectively). Relations to other, previously known codes are discussed as well.

Bill Cherowitzo: Hyperovals in Hall Planes of Even Order Revisited

Several hyperovals are known to exist in Hall Planes. Most of these are "inherited", that is, they are hyperovals in Desarguesian planes which remain hyperovals after the derivation process which produces the Hall plane. In the even order case, examples are given by O'Keefe, Pascasio and Penttila (1992), Crismale (1981), and Glynn and Steinke (1993). I will introduce a method that can be used to prove and extend all of these examples as well as producing a non-inherited hyperoval in the Hall plane of order 16.

Dan Daly: How permutations displace points and stretch intervals

Abstract

Jesse Gilbert: Graph Packings and Graph Labelings

If the graph G has the graphs H1 and H2 as edge-disjoint subgraphs, then we say H1 and H2 pack in G. If the graphs H1,H2,...Hk are all isomorphic to H and they partition the edge set of G, then we say G has an H-decomposition. In 1963, Ringel conjectured that for all trees Tn+1, the graph K2n+1 has a Tn+1-decomposition. We have previously proven this conjecture using a counting argument. The present author has previously conjectured that if {Tk} is a linear combination of 2n+1 trees of order n+1 then {Tk} packs in K2n+1. This conjecture is still open. However, we show a special case of the conjecture: We show that if {Tk} is a set of n trees of order n+1 then {Tk} packs in K2n+1.

Oscar Jenkins: Results of the Computer Search for Nonclassical GQ from the Hughes Plane of Order 9

There exist exactly four nonisomorphic planes of order 9, two of which are self-dual: the Galois plane and the Hughes plane. Following the ideas of Jeff Thas and Stan Payne, we search for a new, nonclassical finite generalized quadrangle that would be formed from a nondesarguesian self-dual plane and its point-line dual. In the Hughes plane of order 9, the computer was used to find all dualities of the right type, compose them in the point-line dual with all maps of the collineation group in the point-line dual, and finally check for triangles using a lemma of Stan Payne. The results of this search will be presented.

Soley Jonsdottir: Computing automorphism groups of general linear groups

In this talk I will discuss a method for computing the automorphism groups of general linear groups over finite fields. I will run an automorphism group algorithm by Cannon and Holt generically on GL(2,q) and give explicit generators for the automorphism groups of GL(2,q).

Cayla McBee: Clique finding in graphs and the search for ovoids in polar space

Determining the set of cliques in a graph is an NP-Complete problem causing exhaustive search algorithms to fail on large graphs. Despite the difficulty, clique finding in specific graphs is used to find ovoids in polar space. I will discuss how utilizing the structure of these graphs to reduce excess searching may be an effective tool for finding cliques.

Ross McConnell: Preconditions, postconditions, and certifying algorithms

A certifying algorithm is one that produces a certificate with each output that proves that it has not been compromised by an implementation bug.
For example, many industrial implementations of algorithms for recognizing planar graphs either return a planar embedding, proving that the graph is planar, or simply declare that the graph is non-planar without supplying supporting evidence of this. A certifying algorithm for the problem also returns an instance of one of the well-known forbidden subgraphs that characterize the class to prove that a graph is non-planar.
This approach sidesteps the problem of proving that an implementation is bug-free; it shows only that no bug has compromised the output on a given instance of a problem.
The talk will explore a novel type of algorithm that produces a certificate that one of the following has occurred:
1. A correct output was given;
2. A precondition on the input was violated.
It is not necessary that the certificate provide a simple or efficient means of checking which of these two events occurred. In other words, the certificate proves only a logical implication: if the precondition is met then the output is correct. The advantage of these is that they are often easier to come up with, and they can be chained together as steps of certifying algorithms that have no preconditions.
The technique holds promise in developing certifying algorithms for problems that have no obvious certificates.

Eric Moorhouse: Ultraproduct Constructions

I will describe some uses of ultraproduct constructions in algebra and geometry. (Beware of the oxymoron: these are slick non-constructive constructions which rely on the Axiom of Choice.) There are no surprises here for the experts but plenty of amusing surprises for the rest of us - at least this notion occupied much of my thinking this past spring and I hope to describe it with a fraction of the appeal the subject deserves. Example: We will describe a field K of characteristic zero, having a unique (up to isomorphism) extension of each degree 1, 2, 3, etc. Both K, and the projective plane PG(2,K), are readily described using ultraproducts.

Stan Payne: Searching for a non-Classical Generalized Quadrangle of Odd Order

It is well known that from a regular point X in a GQ of order s there is constructed a projective plane P(X) of order s. Recently J. A. Thas showed that if a GQ of odd order s has two non-collinear regular points X and Y and if the plane P(X) is Desarguesian, then the GQ is classical (isomorphic to the symplectic geometry W(s) with all points regular). His treatment suggested a possible way to start with a non-Desarguesian plane and construct a GQ. Our student Oscar Jenkins has used an involved computer search to show that the Hughes plane of order 9 cannot be used in this specific way to build a GQ. We give a preliminary report on the general construction method and indicate some further steps we plan to take to implement these ideas.

Tim Penttila: Regular systems of unitary polar spaces

A finite field has a (unique) automorphism of order 2 if and only if it has square order, in which case the automorphism is called conjugation. A matrix is unitary if its conjugate transpose is its inverse. The unitary matrices of a fixed size form a group, which operates on a polar space : the incidence structure of subspaces for which the corresponding form vanishes - these are called totally isotropic. (Here the corresponding form is the analog of the complex inner product.) The anisotropic subspaces of dimension one are the points of the polar spaces; those of maximal dimension are the generators.
In 1965, Beniamino Segre introduced the concept of a regular system of a unitary polar space : a set of points that lies on a constant number of generators, this constant number being called its order. The complement of a regular system is a regular system, and a hemisystem is a regular system of order equal to its complement. Segre showed that a regular system of the U(4,q) polar space for odd q is necessarily a hemisystem and gave an example for q=3. Despite considerable interest due to links with codes, partial quadrangles, strongly regular graphs etc., no further examples were found until 40 years later, when an infinite family of hemisystems of the U(4,q) polar space for odd q was constructed.
Here regular systems of the U(6,q) polar space are considered, with 3 infinite families of hemisystems for odd q constructed, each with a large group. In addition, examples of regular systems of the U(6,q) polar space that are not hemisystems are constructed. Moreover, there is a link with the infinite family of hemisystems of U(4,q) : it can be obtained from 2 of the 3 aforementioned families.
Joint work with Antonio Cossidente, University of Basilicata, Italy.

Rachel Pries: A combinatorial problem about Artin-Schreier curves

Artin-Schreier curves are curves defined over a finite field of characteristic p that have an automorphism of order p. This talk is about recent work of myself and Hui June Zhu about a combinatorial problem relating to Artin-Schreier curves. There is a directed graph that arises in studying invariants of these curves such as the genus and p-rank. Understanding this graph gives new insight into the geometry of moduli spaces of Artin-Schreier curves.

Bryan Shader: Minimum rank of matrices described by a graph or pattern over the rational, real or complex numbers

Abstract

Kyle Pula: Maximal Gallai Graphs

We call a simple, complete, edge-colored graph Gallai if it lacks rainbow triangles and say such a graph is maximal if changing the color of any single edge introduces a rainbow triangle. We first show that no finite maximal Gallai graph exists and then construct a countably infinite example.

Timothy Vis: Being Discrete: Hinding behind Bits

Abstract

Petr Vojtechovsky: Missing lengths of rainbow cycles

In a complete edge-colored graph K, let S denote the set of all n such that K contains no rainbow n-cycles. We show that S is a monoid under the operation x*y = x+y-2, and that it must contain an arithmetic progression with period 1, 2 or 4. The following question is difficult: If m belongs to S, what is the least integer bigger than m in S?

Schedule of the Meeting (subject to change)

The lectures will be held in Wagar 133. The coffee breaks are in Weber 117. The registration is in Weber, in front of Weber 110, starting 12:40.

Thursday August 2

Friday August 3



File translated from TEX by TTH, version 3.74.
On 31 Jul 2007, 16:07.