These are the Department of Mathematical and Statistical Sciences Legacy Pages

We give correspondences between classes of bipartite graphs and combinatorial (0,1)-matrices, some old and some new. Depending on one's perspective, the relationships may help provide structure theorems for the graph classes, or structure theorems for the (0,1)-matrices. Specifically, the adjacency matrices of interval bigraphs, interval-point bigraphs, X-, Y-consecutive bigraphs, convex bigraphs, and unit interval bigraphs correspond to various classes of (0,1)-matrices with combinatorial properties. The matrix classes put in correspondence to these graph classes are the zero-partitionable matrices, those with consecutive 1's in rows, or in columns, or both, and those with a monotone consecutive arrangement. Other classes of graphs have known containment relationships among the aforementioned; the matrix characterizations have provided insight into their structure. Namely, we give a few results regarding the class of bipartite probe interval graphs, and the unit probe interval graphs, which follow from, or have been inspired by, the research presented.

This seminar talk will introduce the chromatic and circular chromatic numbers of a digraph. After discussing the basics, I'll recall a famous paradoxical theorem of Paul Erdos from 1959. This will set the stage for the presentation of a digraph analogue of Erdos theorem. The proof uses probabilistic ideas and a surprising application of a fact from basic algebra. Which fact shall remain top secret until the key moment when it is needed.

Refreshments will be served.

A pattern of a matrix M is a (0,1) matrix which replaces all non-zero entries of M with a 1. Work in quantum algorithms in discrete situations has given rise to study of graphs and digraphs whose adjacency matrices are the pattern of a unitary matrix. A necessary condition for a matrix to be unitary is a property known as combinatorial orthogonality. If the adjacency matrix of a irected graph forms a pattern of a combinatorially orthogonal matrix, we say the digraph is quadrangular. In particular, we look at the quadrangular property in tournaments. We give some necessary conditions for tournaments to have the quadrangular property. We classify quadrangular tournaments which are not strongly connected in terms of a lower bound on their domination number. We also give some constructions for quadrangular tournaments, and introduce a number of open problems.

Refreshments will be served.

Please note this seminar is on Wednesday at 11AM. http://carbon.cudenver.edu/~egethner/jphutchinsonAbstract.html

We consider a variety of visibility graphs, related theorems and algorithms for their characterization and layout. We represent graphs in the plane by horizontal line segments (bars) with vertical visibility (bar-visibility graphs), by rectangles in the plane with horizontal and vertical visibility (rectangle-visibility graphs), and by arcs from concentric circles with radial visibility (polar visibility graphs). We also venture into 3-dimensions using parallel rectangles with upward visibility, onto the cylinder, the Moebius band, and the torus with parallel line segments and orthogonal visibility. In some of these depictions a graph characterization is given, for others the problem is NP-complete. Finally we introduce the "visibility number" of a graph, the minimum t with which vertices can be represented each by t or fewer bars in the plane and edges by vertical visibility; we study how this parameter performs on familiar graphs. These results include joint work with P. Bose, Y-W. Chang, A. Dean, M. Jacobson, J. Lehel, T. Shermer, A. Vince, and D. West.

Pizza will be served afterwards!

SRT division, as it was discovered in the late 1950s represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. To tackle this problem almost 50 years later we can describe the original version of SRT division as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem (at least for computer science). In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov-Ornstein Theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms. This is joint work with Nicholas Pippenger.

Refreshments will be served.

This is joint seminar with the UCD Computer Science Dept. Please note the seminar is on Wednesday at 11AM.

Take the 3n sides of n triangles and glue them together in pairs so as to form an orientable surface (with all (3n-1)(3n-3) ... 3 1 glueings being equally likely). What is the topolgy of the resulting surface? This question arose in the study of 2-dimensional quantum gravity in string theory. Our results (this is joint work with Kristin Schleich of Physics and Astronomy at UBC) are most conveniently expressed in terms of a parameter h = chi + n/2, where chi is the Euler characteristic of the surface. Simulations and results concerning similar models suggest that

Ex[h] = log(3n) + gamma + O(1/n)

and

Var[h] = log(3n) + gamma - pi^2/6 + O(1/n),

where gamma=0.5772... is Euler's constant. Though we cannot confirm these precise conjectures, we have shown through the analysis of a randomized algorithm that

Ex[h] = log n + O(1)

and

Var[h] = O(log n).

I will describe these proofs, and those of several related results concering random surfaces.

In 1960, Claude Berge introduced the concept of perfect graphs. A graph is perfect if, for all induced subgraphs, the size of the largest clique is equal to the chromatic number. The chromatic number of a graph is defined to be the smallest number of colors that can be assigned to the vertices so that adjacent vertices are assigned different colors. The clique number of a graph is the largest number of pairwise adjacent vertices. This presentation will introduce some of the main results of perfect graphs. Some classes of perfect graphs such as bipartite, chordal, comparability, interval, and permutation graphs will be discussed as well as their applications.

Master's Advisor: Rich Lundgren

Refreshments will be served.

A tube graph is a generalization of an interval graph. We consider, instead of the intersection graph of intervals on a line, the intersection graph of n-dimensional polytopes contained in a "tube" of n parallel lines in n-space. This definition is motivated by the analogous definition of a tube poset; the polytopes must be contained in the tube for the partial order to be well-defined. It turns out that every graph is a tube graph. The next natural question to ask is, are tube graphs using polytopes of one type also tube graphs using polytopes of a different type? For example, is every tetrahedron graph also a trapezoid graph? There are an infinite number of questions of this type. I will talk about some work, by myself and others, that answers a finite number of them. Refreshments will be served.

Mathematicans prefer graphs drawn with their symmetries displayed. In this talk we see that every graph has an embedding in Euclidean space in which the isometry group of the embedded vertices induces precisely the automorphism group of the graph. This is called an isometric embedding. We also address the question of the minimum dimension necessary for an isometric embedding, and look at which graphs have such an embedding in the plane.

Refreshments will be served.

The history of the four-color theorem and Kempe's faulty proof will be presented, followed by several counterexamples. A new nine-vertex counterexample will be shown and it will be proved that there are no counterexamples on eight or fewer vertices. Finally, some introductory work on labeling a planar graph will be presented. Refreshments will be served.

The use of computers in theoretical mathematical research has been growing exponentially since the mid 50's. Over this period, editors and authors have had to grapple with the question of how to present material obtained by computers in the literature. The spectrum of solutions is rather wide, due, in part, to the "newness" of the technology conflicting with long held views concerning the rigorous standards of mathematical writing. Today, with much more experience in the use of computers, we should think about the issues involved with the aim of developing reasonable guidelines for editors and authors that the mathematical community can be comfortable with. In this talk I will examine some of these issues, drawing examples mostly from the field of finite geometries. The talk will be partially historical, partially philosophical and partially subjective. My aim is to generate interest in discussing this issue before it becomes a problem that the mathematical community has to solve.

Certain graphs in the plane can be represented with a simple geometric layout, using horizontal bars for vertices and vertical visibilities for edges. The consideration of such bar-visibility graphs, or BVGs for short, was motivated by problems arising in the layout of VLSI circuits. BVGs have a simple characterization and are recognizable in linear time. The study of BVGs has been generalized in numerous ways (e.g., other geometric objects for vertices, multiple visibility directions, and 2-dimensional surfaces other than the plane), and it has been specialized to BVGs with all bars of equal length. This talk is a survey of some of what is known, and some of what remains to be discovered, about several variations of BVGs.

The 7th Annual Rocky Mountain Discrete Mathematics Days will take place August 4-5 at the CU-Denver Mathematics Department. Talks will run from 1:00-5:40 on Monday, and from 9:00-5:30 on Tuesday. A complete schedule is given below. The conference is partially support by the National Science Foundation.

1:00-1:10 Opening Remarks

1:10-2:10 From Homomorphisms To Interval Bigraphs Pavol Hell, Simon Fraser University

Abstract: Graph homomorphisms generalize colourings and model many assignment type problems. The complexity of homomorphism problems is not well understood. However, the complexity of a natural variant, the list homomorphism problem, has recently been classified. It turns out that the cases that can be solved in polynomial time all take advantage of some kind of interval-graph-like structure. I will explore the connections and give some new results and algorithms about the related structured graphs. This is joint work with Huang Jing; some results are joint also with Tomas Feder. Work of Corneil, Mueller, McMorris, Lundgren, Brown, Flink, Miller, and others, will also be mentioned. 2:15-2:45 Interval k-graphs and partial orders Stephen Flink ,UC-Denver

Abstract: Interval k-graphs generalize interval graphs, probe interval graphs, and interval bigraphs. We give necessary and sufficient conditions for an interval k-graph to be the complement of a comparability (transitively orientable) graph, in terms of the interval representation and discuss progress towards a characterization in terms of forbidden substructures.

2:50-3:20 Tube Graphs and Orders Josh Laison, Colorado College

Abstract: An interval graph is a graph whose vertices are labeled with intervals on the real line, with an edge between vertices if and only if their corresponding intervals overlap. Many generalizations of interval graphs have been studied. The definition of tube graphs was designed to subsume a number of these generalizations as special cases, and introduces many interesting new generalizations. Current research focuses on distinguishing these various generalizations in a Venn diagram. I will give an overview of known results, and introduce a few of the many open questions.

3:20-3:50 Coffee Break

3:50-4:20 Kempe's Faulty Proof William Springer, UC-Denver

Abstract: A brief history of the four-color theorem and Kempe's faulty proof will be presented, followed by several counterexamples. A nine-vertex counterexample will be shown and proved to be minimal. Some introductory work on labeling planar graphs will be presented.

4:25-4:55 k -stable tournaments of small orders Art Busch, UC-Denver

Abstract: A k-stable tournament T is a tournament where every tournament obtained from T by reversing at most k arcs is an all kings tournament. By counting 3-cycles, it can be shown that a k-stable tournament T has at least 4k+3 vertices, with equality if and only if T is doubly regular. A more complicated counting argument is used to show that no k-stable tournament exists of order 4k+4.

5:00-5:30 Geometric proofs of the existence of Parter and Fiedler vertices in trees In-Jae Kim, University of Wyoming

Abstract: Symmetric matrices A that have an eigenvalue lambda of multiplicity at least 2, and whose graph is a tree are studied. We study two types of vertices: a Fiedler vertex is an index i for which each eigenvector of A corresponding to lambda has ith coordinate 0, and a Parter-vertex is an index i such that m_A(lambda)+1=m_{A(i)}(lambda), where m_B(lambda) is the multiplicity of lambda as an eigenvalue of B, and A(i) is the principle submatrix of A obtained by deleting row and column i. We give geometric characterizations of Parter vertices in terms of Fiedler vertices, and prove the existence of Fiedler and Parter vertices.

5:35-6:05 Several Characterizations For Unit Interval Bigraphs Dave Brown, UC-Denver

Abstract: An interval bigraph is the bipartite intersection graph of two distinct families of intervals in which vertices are adjacent if and only if their corresponding intervals overlap and each belongs to a distinct class of intervals. We investigate the case where all intervals among the two families are of the same length (the unit interval bigraphs or UIBGs), and give several characterizations, some old and some new, which relate the UIBGs to many other classes of graphs and combinatorial objects. Namely, we show the equivalence of UIBGs, bipartite permutation graphs, and asteroidal triple-free bipartite graphs. If among all intervals comprising the distinct families, no interval properly contains another, then we have a proper interval bigraph or PIBG. We give new proofs showing the eqivalence PIBGs and the aforementioned via a total ordering of the vertices, and hence to the strong ordering that characterizes bipartite permutation graphs. Also, by placing these results in context with (0,1)-matrices, we are able to give a structure theorem for the (0,1)-matrices with a monotone consecutive arrangement -- a condition stronger than having both the consecutive 1's property for rows and for columns simultaneously.

Dinner at P.F. Chang's

Schedule for Tuesday, August 5th

9:00-10:00 On Visibility Graphs Joan P. Hutchinson, Macalester College

Abstract: We consider a variety of visibility graphs, related theorems for their characterization, and algorithms for their layout. We'll compare these with interval and intersection graphs - though they seem similar, the similarities are in most cases superficial. Specifically we represent graphs in the plane by horizontal line segments (bars) with vertical visibility (bar-visibility graphs), by rectangles, aligned with the x- and y- axes, with horizontal and vertical visibility (rectangle-visibility graphs), and by arcs from concentric circles with radial visibility (polar visibility graphs). The first and third type of graphs are completely characterized; recognizing the second is an NP-complete problem. We consider special cases for these graphs, for example when all bars have unit length and all rectangles are unit squares. We discuss also the visibility number of a graph, that is, the minimum t with which vertices can be represented each by t or fewer bars in the plane and edges by vertical visibility; we study how this parameter performs on familiar graphs. These results include joint work with P. Bose, Y-W. Chang, A. Dean, E. Gethner, M. Jacobson, J. Lehel, T. Shermer, A. Vince, and D. West.

10:05-10:35 Maximal Clique Partitions of Different Sizes Chariya Uiyyasathian, CU-Denver

Abstract: A maximal clique partition of a graph is a family of its maximal complete subgraphs that partition its edge set. Many graphs do not have a maximal clique partition while some graphs have more than one maximal clique partitions. It is harder to find graphs in which maximal clique partitions have different sizes. The line graph of K_5 is a well-known example. In 1982, Pullman et al. asked if there is a graph with fewer vertices than the line graph of K_5 with this property. This talk confirms that there is no such a graph.

10:35-11:00 Coffee Break

11:00-11:30 A Characterization of Cycle Free Unit Probe Interval Graphs Dave Brown and Richard Lundgren*, UC-Denver and Li Sheng, Drexel University

Abstract: Probe interval graphs were introduced about 10 years ago for mapping of DNA. A graph is a probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and the two intervals have a nonempty intersection. Interval graphs are probe interval graphs with the set of nonprobes empty. Unit probe interval graphs require that all the intervals assigned to the vertices must have the same length. In this talk we give a forbidden subgraph characterization of cycle free unit probe interval graphs. We compare this result to a characterization of unit interval bigraphs given in another talk at this meeting. Also we discuss the characterization problem for bipartite unit probe interval graphs.

11:35-12:05 Dirac & Ore type results for tournaments Mike Jacobson, UC-Denver

Abstract: In this talk, several problems about the existence of special directed paths and cycles in tournaments will be discussed. Minimum degree and degree sum results will be given for some of these questions. In addition, constructions will be shown indicating the �tightness� of these results.

12:05-1:30 Pizza Party

1:30-2:00 Orbit computation and applications in finite geometry Anton Betten, Colorado State University

Abstract: Computing ``interesting'' discrete structures usually amounts to solving two problems: At first, the objects need to be constructed (usually by computer search). Secondly, as one is only interested in the essentially distinct types of objects, some kind of isomorphism testing is done on the set of solutions. The purpose of this talk is to improve on that by integrating both tasks into one. That is, the combinatorial conditions which come from the nature of the objects, and the action of the symmetry group. It turns out that group actions are very effective in cutting down the search tree to only a fraction of the original search tree. In the end, the solutions which survive these two kinds of tests form a transversal of the isomorphism classes of objects, i.e. each object is constructed once and only once. As an application, we talk about ongoing work on the classification of linear codes with prescribed minimum distance and flocks over ovals.

2:05-2:35 Flocks of the Cone over the Segre Oval Carey Jenkins, UC-Denver

Abstract: A branch and bound algorithm implemented on the Beowulf cluster has discovered a new nonstar (hence nonlinear) flock in PG(3, 32). Underway is an effort to apply the Schrier-Simms algorithm to find more. The algorithm has the ability to give the flocks up to isomorphism, as well as prune the search tree.

2:40-3:10 When does x^6 + x + b = 0 have a zero in GF(2^e) with e odd? Stan Payne, UC-Denver

Abstract: In studying flocks of the cone over the Segre hyperoval it becomes necessary to find those elements b in GF(2^e) with $e$ odd for which x^6 + x + b = 0 has no solution in GF(2^e). This is a very tricky problem, but a solution has been given in a paper by Ronald Evans, Henk Hollmann, Christian Krattenthaler and Qing Xiang. We discuss this equation and present their solution with a brief introduction to their proof. (See the abstracts by Carey Jenkins and Anton Betten.)

3:10-3:50 Coffee break

3:50-4:20 Quadrangular Tournaments and Orthogonal Matrices Dustin Stewart, UC-Denver Abstract: The pattern of a matrix $M$ is the $(0,1)$-matrix which replaces all non-zero entries of M with a 1. Work in quantum algorithms in discrete situations has given rise to study of graphs and digraphs whose adjacency matrices are the pattern of a unitary matrix. A necessary condition for a matrix to be unitary is a property known as combinatorial orthogonality. If the adjacency matrix of a directed graph forms a pattern of a combinatorially orthogonal matrix, we say the digraph is quadrangular. In particular, we look at the quadrangular property in tournaments. We give some necessary conditions for tournaments to have the quadrangular property. We classify quadrangular tournaments which are not strongly connected in terms of a lower bound on their domination number. We also give some constructions for quadrangular tournaments, and introduce a number of open problems.

4:25-4:55 The Knight�s Tour Problem John J. Watkins and Yulan Qing, Colorado College

Abstract: The Knight�s Tour Problem asks whether a knight can begin at one square on a chessboard, visit each square on the board in a sequence of knight�s moves, and then return to the beginning square. In other words, this problem asks whether the knights graph for the standard chessboard is Hamiltonian. We will survey what is known about this famous problem, beginning with early work on the problem by people such Euler and de Moivre, answering such questions as which rectangular chessboards have knight�s tours, looking at tours on other surfaces such as the torus and the cylinder, and presenting new results both for knight�s tours on cubes and boxes and for 3-dimensional knight�s tours. (You might want to ask yourself: how should a knight move in three dimensions?)

5:00-5:30 A covering problem Bryan Shader, University of Wyoming

Abstract: We determine the smallest number of nonzero entries in an n by n nonnegative integer matrix A=[a_{ij}] which has all line sums n, and is nearly lower triangular (i.e. a_{ij}=0 for all i and j with j>i+1.) This problem is then related to the problem of efficient majorization of vectors.

The problem of determining whether a graph contains a "long" path or cycle has been around for over 150 years. In fact, dating back to when the entrepreneur, Hamilton, tried to market his "Around the World" game. Since that time primarily over the last 50 years, there has been a preponderance of work by combinatorialists to better understanding the underlying cycle structure of graphs. In this (these) talk(s), a survey of the known results and problems pertaining to the existence of long paths and cycles in graphs will be presented.

A graph G is cycle extendible if for every non Hamiltonian cycle C of G, there is a vertex v not on G, so that C+v has a spanning cycle. In this talk I will introduce the idea of cycle extendability, and show a connection between this property and chordal graphs. In addition the following result will be given:

Theorem. If G is a Hamiltonian interval graph then G is cycle extendible.

This result takes the first step at solving a 20 year old conjecture of George Hendry, which is that all chordal Hamiltonian graphs are cycle extendible.

This talk will provide a gentle introduction to association schemes, with an emphasis on how they arise from certain combinatorial objects such as generalized quadrangles, designs, and doubly regular tournaments. Association schemes provide useful machinery which can be used to study sufficiently regular combinatorial objects, and suggest directions for studying those which don't have quite enough regularity.

Interval graphs originated in Benzer's original work on DNA in 1959. Over the years they have been thoroughly investigated and generalized, mostly because of their usefulness in many applications and the nice properties they exhibit. More recently, in 1996, Zhang introduced probe interval graphs as a means of studying various problems associated with physical mapping of DNA. Interval graphs are a special case of probe interval graphs. The definition of probe interval graphs leads naturally to an extension for bipartite graphs called interval bigraphs, and we have recently extended this class to a new class called interval k-graphs.

In this talk we will start by reviewing some of the classical results on interval graphs. We will then look at these new variations and discuss general properties, forbidden substructures, and some new and very new characterizations of these graphs. Some of the talk will cover joint work with my graduate students Dave Brown, Steve Flink and Cary Miller, but there will also be considerable discussion of the recent work of several other authors on these topics. We will also discuss several open problems and suggestions for future research.

Interval graphs and their variations have applications in many areas including scheduling, computer science, archaelogy, psychology, biology, {0,1}-matrix theory, etc. The talk will be understandable by a general math audience.

PROJECTIVE PLANES are just bipartite graphs of diameter 3 and girth 6 with every vertex having at least 3 neighbours.AFFINE PLANES can be constructed from projective planes by deleting a vertex and all its neighbours, and this process is reversible. The oldest way to construct affine and projective planes is to construct an algebraic system of some kiind and then mimic the construction of the real affine plane from the real numbers. A TRANSLATION PLANE is an affine plane with the property that for any two points, there is a translation taking the first to the second. The algebraic systems corresponding to translatioin planes are called QUASIFIELDS. All finite quasifields are constructed by modifying the multiplication, in some way or other, of finite fields. (It is known that the nuber of elements of a finite quasifield - the order of the corresponding plane - must be a power of a prime number.) In order to show that the modified field is a quasifield, knowledge about solutions of equations over finite fields is needed. One way to keep the problem simple is to keep the degrees of the equations low. Here, I will explain about solutions of quadratic and cubic equations in one variable over a field of even order, and use this to construct new translation planes of even order.

Note: This is joint work with Bill Kantor.

Consider the following variation of the classic Turan-type extremal problem. Let pi be an n-element graphical sequence, and let sigma be the sum of the terms in pi. Let G be a graph. The problem is to determine the smallest integer m such that any n-term graphical sequence pi having sigma(pi) greater than or equal to m has some realization containing G as a subgraph. Here we present the (brief and still developing) history of this problem.

Note that this problem varies from the Turan problem which requires all realizations of such sequences to contain G.

We also develop a more general problem by considering other properties. That is, we say S is potentially P-graphic, for some graph property P, if some realization G of S has property P. We also briefly survey several results of this type.

An interval bigraph (IBG) is the intersection graph of two families of real intervals in which vertices are adjacent if and only if their corresponding intervals overlap and belong to distinct families. At this point in time IBGs are forbidden-subgraph-characterization-free. However, if we restrict all intervals to be of length one, obtaining the unit interval bigraphs (UIBGs), we have a class of graphs that are equivalent to roughly nine other (some well-known, some not-so-well-known) classes of graphs and a few structural properties. I will discuss a few of these equivalences in detail and (in the interest of time) only mention the others I know of at this point. To name a few of the classes that are equivalent to UIBGs: bipartite permutation graphs, bipartite trapezoid graphs, bipartite function graphs, bipartite bounded tolerance graphs, bipartite cocomparability graphs, bipartite asteroidal triple-free graphs, and more.

A probe interval graph (PIG) is a graph with vertex partition V = (P,N) and an interval assigned to each vertex so that vertices are adjacent if and only if their corresponding intervals overlap and at least one belongs to P. PIGs are also forbidden-subgraph-characterization-free in general, but Li Sheng has given such a characterization in the case for trees. A unit probe interval graph (UPIG) is a PIG in which all intervals in some representation can be made to have length one. I will discuss recent results by Rich Lundgren, Li Sheng and myself regarding UPIGs in the case for trees and in case the UPIG is bipartite, which will realte to recent work by Bogart, Jacobson, Langley and McMorris.

A tournament is an orientation of a complete graph. It is well known that every tournament contains a hamiltonian path. In this talk, hamiltonian paths that include a specified arc are considered. Several sufficient conditions are presented, and a general description is given for tournaments with at least one arc on no hamiltonian path. From these results, some sufficient conditions are given for arc-traceable tournaments (tournaments in which every arc is on some hamiltonian path).

We first introduce the notion of finite generalized quadrangle (FGQ) and explain what is an elation about a point. This leads to the notion of an elation GQ.Then we review what is a group action on a set and remind the audience of the well-known orbit-counting lemma (known erstwhile as ``Burnside's Lemma'').A rather elementary application of the orbit-counting lemma is used to give a fairly simple criterion for determining when the set of elations of a finite generalized quadrangle (FGQ) is a group. The criterion is then applied to some of the known families of GQ.

This is joint work with Koen Thas of the University of Ghent, Belgium.

This will be a gentle introduction/tutorial to the subject of finite fields. We will concentrate on constructions, representations and uses related to cryptology. No background will be assumed, but familiarity with the algebraic concept of a group will smooth over some of the rough spots.

The pattern of a matrix M is a (0,1) matrix which replaces all non-zero entries of M with a 1. Studying the patterns of orthogonal matrices has applications in areas ranging from design theory to quantum physics. We look at some necessary combinatorial conditions relating to this problem and in particular apply them to tournament matrices. As it stands, only one tournament matrix is known to be the pattern of an orthogonal matrix. We will discuss some of the hopes and problems we have had in searching for these matrices.

Let p be a point of a generalized quadrangle (GQ). An elation about p is a collineation of the GQ that fixes p linewise, and fixes no point not collinear with p, or is the identity map. If a GQ admits a group G of elations acting regularly on the set of points not collinear with p, then we say that the GQ is an elation GQ (EGQ). A well known EGQ is H(3,q^2), which is a hermitian surface in the projective space PG(3,q^2). In this talk we set q = 2^e. Until recently it was generally thought that all elations of H(3,q^2) (about a given point p) formed a unique subgroup of the full collineation group of H(3,q^2). Tim Penttila of the University of Western Australia discovered (through a computer search) some "exotic" elation groups of this classical EGQ. In this talk, after giving sufficient background material, we give (for any q = 2^e) an algebraic description of these new elation groups, and prove that these "exotic" groups are non-isomorphic to the "usual" group of elations. We also show that we have discovered all possible elation groups of H(3,q^2). In addition, we hope to show that all these "exotic" groups are isomorphic, so that there are only two elation groups of H(3,q^2) up to isomorphism.

We discuss maximal-clique partition problems with emphasis on existence, beginning with a necessary and sufficient condition for a line graph to have a maximal-clique partition. There are three clique parameters of a graph G: the clique covering number cc(G), the clique partition number cp(G), and the maximal-clique partition number mcp(G). We evaluate all three clique parameters for line graphs. In addition, we discuss the complexity of the problem of finding maximal-clique partitions of line graphs.

We then investigate graphs with maximal-clique partitions of different sizes. The graph L(K_5) has two maximal-clique partitions of different sizes. We confirm that there are no graphs with maximal-clique partitions of different sizes with fewer vertices than L(K_5) has. Also, for each natural number n, we give a clique-inseparable graph with n maximal-clique partitions of n different sizes.

We investigate the question of the existence of a graph G with cc(G) = cp(G) < mcp(G), and find infinitely many graphs satisfying this property.

Finally, we solve another existence problem regarding graphs with cc(G) < cp(G) < mcp(G). In 1982 Pullman, Shank and Wallis constructed a graph of 11 vertices satisfying cc(G) < cp(G) < mcp(G) and asked whether or not there exists a graph on fewer vertices with cc(G) < cp(G) < mcp(G). We confirm that there is no such graph.

Many questions in discrete math can be reformulated algebraically in terms of finding an orbit or stabilizer under some group action. For example, determining if two graphs are isomorphic is polynomial-time reducible to finding the stabilizer of a set. These problems are not known to have polynomial time complexity, but there is evidence that they are not NP-complete. The theory of Schreier and Sims allows computer computations of large groups, not by storing group generators, but by storing transversal representatives in Schreier Trees. Keeping the trees shallow is a goal, and we'll examine the symmetries of a cube and find stabilizers of cones in projective space.

M.C. Escher used a single unit square motif with overlapping weaves that is asymmetric under rotation, reflection and inversion (the reversal of the order of the weaves) to construct larger, more complex 2 by 2 Escher tiles that he used to tile the plane.

He catalogued a total of 23 inequivalent tilings of these 2 by 2 tiles under the operations of translation and rotation. This result has since been verified using Burnside's counting lemma. Here we will apply Burnside to demonstrate that there are 1124 inequivalent tilings if we also include the operations of reflection and inversion.

In recent years the unconstrained quadratic binary program has emerged as a modeling and solution framework of surprising versatility and computational promise. In this talk, I will review these developments (based on joint work with Fred Glover and others) and present some new results for several important combinatorial problems, including clique partitioning and related problems on graphs.

Interval k-graphs (IKGs) are a natural extension of both interval bigraphs and probe interval graphs. I will describe containment relations between interval k-graphs and these other classes in terms of interval homomorphisms, and show some general properties of interval homomorphisms.

The relationship between interval k-graphs and cocomparability graphs (graphs whose complements admit a transitive orientation) is explored, and a partial characterization is given in terms of the interval representation. In particular, the partial orders of width 4 whose cocomparability graphs are interval k-graphs are completely described. In addition, a representation of cocomparability interval k-graphs as pure intersection graphs is outlined.

At the Third Pythagorean Conference held in June, 2003,on the island of Rhodos, Greece, W. H. Haemers gave a talk in which he developed a technique for obtaining restrictions on the parameters of self-dual designs whose incidence matrices are singular. This extends traditional results of the form obtained when AA^T is observed to be a nonzero square for some matrix associated with a design. The main result says that if N is the incidence matrix of a self-dual design, then the product of the positive eigenvalues of NN^T is an integral square.

Our favorite application is the following: If there is a self-dual generalized quadrangle of order s and if s is congruent to 2 mod 4, then 2s must be a square.

The proof techniques involve only basic linear algebra used in a novel way. We plan to give more or less complete proofs of the results involved, and the talk should be easily understood by any first year graduate student.

In the cycle-free case, the class of tolerance graphs conicides with the class of cycle-free interval bigraphs. We show that in general, the class of interval bigraphs contains tolerance graps that are triangle-free (and hence bipartite). By extending this result, we obtain a characterization of triangle-free tolerance graphs. We also give separating examples to show that this containment relationship is proper.

An (n,k)-weighing matrix M is an n by n (0,1,-1) - matrix in which every row and column has exactly k non-zero elements and M*M^T = kI. the support of a matrix A is a (0,1) - matrix with a 1 in the (i,j) position if and only if the (i,j) entry of A is not equal to 0. In particular, we have been searching for a weighing matrix whose support is the adjacency matrix of a quadratic residue tournament. In this talk we give some basic background on this problem, and discuss some of our search algorithms and their implementation on the Beowulf cluster.

If D is a digraph, then a subset K of V(D) is a king set of D provided D[K] is discrete and for each y in V(D) \ K there is some x in K for which the directed distance from x to y is less than three. We characterize the digraphs which have a uique king set. From this we obtain a result showing that any digraph without sources has at least two king sets. We also apply the main theorem to show precisely which dinovas have exactly one king set. We use the term dinova to denote any digraph whose underlying graph is a nova.

This talk is based primarily on the paper Digraphs with Unique King Sets by S. Bowser and C. Cable, which has been submitted for publication.

With the help of the audience Leonard and Ryan will perform an amazing card trick. Then Ryan will present the mathematical explanation of the trick. In the common sense of the word "elementary," this is an elementary (but not necessarily simple) talk that should be enjoyed by all.

Every tournament contains a hamiltonian path and Redei showed the surprising result that every tournament has an odd number of such paths. Furthermore, a tournament has exactly one hamiltonian path if and only if the tournament is transitive. We consider the tournament obtained from a transitive tournament by reversing all of the arcs on this unique hamiltonian path, and show that the number of hamiltonian paths in such tournaments follows the "tribonacci" recurrence, i.e., a(n) = a(n-1) + a(n-2) + a(n-3), where n is the number of vertices in the tournament.

The 2004 Meeting of the Rocky Mountain Section of the Mathematical Association of America will be held April 16 - 17 at Colorado College. For all the information you need please check the internet at

Rocky Mountain Section Mathematical Association America

The two main invited speakers are

Lowell Beineke

Friday night banquet address: SPLENDOR IN THE GRAPHS

9:00 a.m. Saturday Keynote Address: GRAPHS ARE FINALLY SURFACING

Robin Wilson

Friday at 4:30 p.m. - FOUR COLORS SUFFICE: HOW THE MAP

PROBLEM WAS SOLVED

An application in cryptology has led to an interesting geometric question concerning sets of points in a projective plane. I am investigating this question by using the graph theoretical concepts of 1-factors and 1-factorizations of complete graphs.

In this talk I will concentrate on the graph theoretic aspects of the geometric problem and introduce just enough geometry to make the constructions I use meaningful.

A near polygon is a connected graph of finite diameter satisfying the property that for every vertex x and every maximal clique M there exists a unique vertex in M nearest to x. Ordinary 2d-gons are probably the simplest examples of near polygons. Shult and Yanushka showed that there is a connection between these graphs and certain line systems in Euclidean spaces. We will explain this connection. We will define some nice classes of near polygons and sketch how certain algebraic techniques, like eigenvalue techniques, can be used to show the nonexistence of certain near polygons. We will also discuss some recently obtained results on the topic.

Every tournament on n vertices contains a transitive sub-tournament on log(n) vertices. We denote the size of the largest transitive sub-tournament of T as tr(T). For sufficiently large n there exists a tournament T with

tr(T) <= 2log(n) + 1.

We seek to improve these results when the score sequence of T is given, and we show that given the score sequence of an n-tournament, that there is always some tournament T realizing this score sequence with tr(T) >= (n+1)/2. This leads to the question of the largest possible difference tr(T) - tr(T*) when T and T* have the same score sequence.

A brief overview of 2-factors in graphs will be presented and then a new result on the existence of a certain 2-factor in hamiltonian graphs with a given minimum degree condition will be shown. Other new results will be given and related questions will be posed.

Let S=GQ(s,t)be a generalized quadrangle with parameters (s,t), and let p be a point of S. Then an elation of S about p is a collineation of S that fixes all lines through p and acts semiregularly on the set of points not collinear with p. If a GQ admits a group E of elations about a point p acting regularly (i.e., sharply transitively) on the points not collinear with p, then the GQ is called an Elation Generalized Quadrangle (EGQ). Furthermore, the EGQ can be constructed as a coset geometry using certain subgroups of E. We have recently discovered an algebraic description of an exotic set of q^2-1 isomorphic elation groups of the EGQ known as H(3,q^2) which are non-isomorphic to the standard elation group. Furthermore, we have found necessary and sufficient conditions that the coset geometry of a set of subgroups be an EGQ. These conditions suggest a rather simple classification of all EGQ constructed from these exotic elation groups. In this talk we will sketch the development and description of the exotic elation groups and explain the necessary and sufficient conditions described above. We will also mention the implied conjecture and the computer search results concerning this conjecture and suggest some related open problems.

A triangulated polygon is a 2-connected maximal outerplanar graph. A unit bar-visibility graph (Unit BVG for short) is a graph whose vertices can be represented by disjoint, horizontal, unit-length bars in the plane so that two vertices are adjacent if and only if there is a non-degenerate, unobstructed, vertical band of visibility between the corresponding bars.

The original motivation for studying Bar-visibility graphs was the design of electronic circuits; another application is the display of data, using bars `fattened' into rectangles that hold labels, with relations between data items represented by visibility bands.

We give combinatorial and geometric characterizations of the triangulated polygons that are Unit BVG's. To each triangulated polygon G we assign a character string with the property that G is a Unit BVG if and only if the string satisfies a certain regular expression. Given a string that satisfies this condition, we describe a linear-time algorithm that uses it to produce a Unit Bar Visibility layout of G.

P.S. This is joint work with Alice Dean and Joan Hutchinson.

In 1994 Zhang introduced and used the probe interval graph model in the human genome project as a more powerful and flexible tool than an interval graph model for the assembly of contigs in the physical mapping of DNA. G = (V,E) is a probe interval graph (PIG) with respect to a partition (P,N) of V if vertices of G correspond to intervals on a real line and two vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is in P. Unlike the situation with interval graphs, it has been difficult to find good characterizations of PIGs, particularly in terms of forbidden subgraphs. So the approach has been to restrict the problem to certain classes of graphs and investigate if good characterizations can be found for these classes. We will start with the work of Sheng (1999) on cycle free graphs. She showed that cycle free PIGs and hence trees that are PIGs can be characterized by two forbidden subgraphs. Two classes that are natural to examine after trees are the classes of 2-trees and the bipartite graphs. It seemed reasonable to expect that each of these classes might have a short list of forbidden subgraphs, but in fact this is not the case. We will talk about the results of Przulj and Corneil (2004) on bipartite graphs. We will also discuss a slight improvement we have on a consecutive ranking characterization using quasi-cliques. If time allows, we will also look at what is known about unit PIGs. Several open problems will be presented.

The goal of this research is to determine the specific conditions under which we can find a simple planar graph G that admits a packing of multiple copies of a tree. We begin by looking at paths, stars, and specific double stars. We restrict our studies to the tight packing where the graph is a triangulation. Tight packings occur with six copies of the tree on 2n vertices and three copies of the tree on n+1 vertices. We would like to extend our specific cases to cover general cases.

Starting with an oval O in the projective plane PG(2,q), around 1967 J. Tits constructed a generalized quadrangle T_2(O) with parameters (s,t) = (q,q). In recent years several examples have been found as subquadrangles of a larger GQ with parameters (q^2,q). When this happen many spreads of the smaller GQ exist (sets of disjoint lines that partition the points). In this talk we report on some efforts to determine all spreads of T_2(O) in order to show in some cases that a given T_2(O) cannot be a subGQ of one with parameters (q^2,q). For q less than or equal to 32 all spreads of all T_2(O) have been found, with the consequence that for q = 32 every T_(O) is known, and for each such GQ it is determined whether or not T_2(O) can be a subGQ as above.

In my talk, I will discuss two new characterizations of interval bigraphs given in a recent paper by Hell and Huang. The main theorem they prove is that the complements of interval bigraphs are circular arc graphs of clique covering number two, in which no two arcs cover the whole circle. In order to illustrate this result, I will rely on previous results of two-clique circular arc graphs.

These graphs have become an important subclass of circular arc graphs and have been characterized in many ways. Trotter and Moore used a list of forbidden subgraphs, which included several infinite families of graphs. Hell and Huang unified these families to achieve the following characterization, similar to a result on interval graphs by Lekkerkerker and Boland: a two-clique graph is a circular arc graph if and only if its complement contains no induced cycles of length at least six and no edge-asteroids. Prior to Hell and Huang's result, M�ller made the following conjecture: a bipartite graph is an interval bigraph if and only if it contains no asteroidal triple of edges and no induced insect.

I will show various counter-examples to M�ller's conjecture given by Hell and Huang, using edge-asteroids and exobicliques, while illustrating their results. The second characterization of interval bigraphs is in terms of vertex ordering and will also be helpful in illustrating the main theorem. The talk will conclude by using these results to show equality among several classes of structured bipartite graphs.

Over the past decade there has been tremendous progress in the area of approximation algorithms. For most canonical NP-hard problems, either dramatically improved approximation algorithms have been devised, or strong negative results have been established, leading to a substantially improved understanding of the approximability of these problems. However, the longest cycle problem has resisted all attempts at devising either positive or negative results. Essentially, there is no known algorithm which guarantees an approximation ratio better than n/polylog(n), and there is no hardness of approximation result that explains this situation. So one feasible way to study the longest cycle problem is to consider some special classes of graphs. In this talk I will discuss progress in the following special classes of graphs: (a) planar graphs, (b) graphs with forbidden minors, (c) graphs with bounded degrees, (d) graphs with very large degrees, and (e) chordal graphs.

In their 1995 paper "On the Classification of Geometric Codes by Polynomial Functions" Glynn and Hirschfeld recast earlier results due to Hamada (1968) and Delsarte (1970) in the language of polynomial functions on finite projective spaces. A function from the set of points of PG(n,q) to the field GF(q) is said to be geometric for dimension i if the sum of its values taken over all points of an i-dimensional subspace is zero, independent of the choice of the i-dimensional subspace. The question of determining the dimension of these (linear) codes is related to an old problem of computing the rank of the points vs. i-subspaces incidence matrix in the projective space (solved by Hamada). The theory has applications in the construction of hyperovals in projective planes of even characteristic. In the talk, I will present and explain these results.

A Zero Knowledge Technique is a cryptographic protocol that allows Alice to prove to a verifier Bob that she knows a secret without revealing the secret and without revealing any information about the proof. That is, neither Bob nor a sinister onlooker can mimic the protocol to another verifier in order to convince the latter that he knows Alice's secret. Some techniques and applictions are explored: proving an n-coloring in a graph, authenticating proprietorship of an account and bit commitments. An effecient method for committing many bits is also proposed.

Abstract:The classification of the finite simple groups is unprecedented in the history of mathematics, for its proof is 15,000 pages long, representing the combined effort of more than 100 mathematicians in over 500 articles published between the late 1940's and the early 1980's. While common knowledge has it that the proof was completed in the early 80's, several gaps were found, one of them serious, and only recently in an article in the AMS Notices has Michael Aschbacher stated that he once again believes that it is a theorem. In this talk we will mention briefly the ultimate result, but will focus more on the long history leading up to the final classification. We will start with Galois in the 1830's and his use of a simple group to prove the insolvability of the quintic, and then discuss the work of Sylow and Burnside. The range problem began around the turn of the century, and we will trace it to the 70's and Marshall Hall's paper on the simple groups of order less than 1,000,000. We will discuss Brauer's pioneering work in the 50's followed by Thompson's odd order and N-groups papers. And of course we will discuss Janko's remarkable discovery of a new sporadic simple group in 1966, the first in 100 years, and an event that sparked an exciting 10 year period when some 21 new sporadic simple groups were discovered. And finally we will look at the work of Daniel Gorenstein, the commander-in-chief or quarterback of the final assault on the problem. I was fortunate to be one of those 100 contributers during perhaps the most exciting period, 1967-1975, and was also fortunate to be a student of Janko. So I will also share some experiences from those years that did not make it into the journals but shed some light on some of the leading characters in the final proof.

27 January 2045 will fall on what day of the week? A friend was born on 26 September 1939. What day of the week was that? In this light-hearted talk we will show how to answer these questions using very elementary number theory.

de Bruijn sequences and the associated de Bruijn digraphs provide an efficient way to represent all possible words of length n using an alphabet of size d. More recently, de Bruijn digraphs have been extensively studied for the use in network design, and several generalizations have been suggested. We consider two additional generalizations. First, we show how a de Bruijn-like digraph can be utilized to find all possible k-subsets of an n-set. We also discuss a class of digraphs known as alphabet-overlap digraphs and show that these digraphs can be thought of as a simple generalization of de Bruijn digraphs. We analyze several properties of alphabet overlap digraphs and their underlying graphs, including diameter, hamiltonicity, connectivity, clique number and chromatic number. Finally, we discuss ways to describe a broad class of digraphs which contains nearly all generalizations of de Bruijn digraphs.

NOTE THE CHANGE IN TIME AND DAY FOR DISCRETE MATH SEMINAR

Suppose that a and b are positive integers, a < b. When can we orient the edges of some complete graph so that the set of distinct out-degrees is exactly {a, b}? That is, when is there a tournament with score set {a, b}? The answer is ~Salways.~T A suitable number of a~Rs and b~Rs can be determined arithmetically using Landau~Rs well-known theorem on score sequences of tournaments, and then one of the constructive proofs of Landau~Rs Theorem (e.g., one by the speaker) can be employed to actually construct a suitable tournament. We seek to bypass this process by combining known tournaments in certain ways and by adjusting scores by arc reversals so as to obtain tournaments with score sets {a, b}. When b ~V a is odd or when b > 2a this is straightforward. When b ~V a is even and b < 2a + 1, such constructions have been elusive. In particular, show me a tournament with score sequence given by (137, ~E, 137, 159, ~E, 159). In this talk we show how to treat these remaining cases, b ~V a even and b < 2a + 1. We comment on extending these ideas to larger score sets.

A triangulated polygon (tp) is a 2-connected, outerplanar, near-triangulation. We prove cases when a tp can be list-colored when degree-2 (resp., degree-3) vertices are given 2-lists (resp., 3-lists) and all others 4-lists. We conjecture that the limiting case is the presence of at least four separating triangles (with all edges interior) due to a non-list-colorable example of A. Kostochka.

Suppose D = (V,A) is a digraph and K is a subset of V. K is a king set of D if both of the following conditions are satisfied: (i) For each vertex y in V \ K there exists a vertex k in K such that either (k,y) is an arc or else there exists an additional vertex z in V \K such that (k,z) and (z,y) are arcs, and (ii) if k1 and k2 are vertices in K, then neither (k1,k2) nor (k2,k1) is an arc.

A digraph whose underlying graph is a path, cycle or nova will be called respectively a dipath, dicycle or dinova. (A digraph D is a nova with center x if D is the union of C2, ... Cn where each Ci is a complete graph containing vertex x and V(Ci) and V(Cj) have only the vertex x in common if i and j are distinct.)

Let m(D) denote the number of minimial king sets of D and let M(D) denote the minimum number of vertices in a king set of D. We give an algorithm for finding m(D) and for finding M(D) when D is either a dipath or a dicycle. We also show how to compute M(D) if D is a dinova, and we give a lower bound for m(D) if D is a dinova.

Our intended seminar speaker for March 29 has called in sick. But please note that our speaker on April 5 will be Stan Wagon. See you then!!

Given a finite set of positive integers A, the Frobenius number f(A) is the smallest number not in the semigroup generated by A. For example, Chicken McNuggets come is sizes 6, 9, and 20. One cannot buy 43 McNuggets, but one can buy M McNuggets for any M > 43; thus f(6,9,20) = 43.

Two new directions in Frobenius computations will be discussed: (1) the use of shortest-path graph algorithms, which solves the problem provided the input integers have no more than about 7 digits, (2) the use of integer-linear programming techniques, which solves the problem provided the input has fewer than 10 entries (but with no limit on the size of the numbers).

Joint work with Dale Beihoffer, Albert Nijenhuis, David Einstein, Danny Lichtblau, and Jemimah Hendry.

A hamiltonian cycle in a graph G is a cycle containing all the vertices of G. For a graph G of order n we say G is k-ordered (1 < k < n+1) if for every ordered set of k vertices there is a cycle in G that encounters the vertices of the set in the given order. If there is a hamiltonian cycle for everry ordered set of k vertices, then we say G is k-ordered hamiltonian. This concept was introduced by Ng and Schultz. The classic results of Dirac and Ore, presenting sufficient contitions for a graph to be hamiltonian, will be generalized to k-ordered Hamiltonian. A series of results will be presented involving degree conditions, generalized degree conditions, neighborhood conditions, and forbidden subgraph conditions that imply k-ordered or k-ordered hamiltonian.

The arcs of the title have the property that their secant lines intersect some line in the smallest possible number of points. These arcs can be used in the design of a geometric secret sharing scheme first devised by Gus Simmons.

I will review the basic concepts involved and then discuss several conjectures that come from our investigations. This is joint work with Leanne Holder of St. Mary's University, San Antonio.

Given a collection of positions in an n-by-n matrix A and another collection in an n-by-n matrix B, when does it happen that, whenever the values of the entries permit B to be the generalized inverse A+, all the remaining entries of A (and B) are uniquely determined? I will consider the case in which the off-diagonal positions in A and B are the same, all the diagonal entries of A are identirfied while noe of those of B are, and all the identified entreis of B are zero. In this event, the arrangement of positions may be described by a directed graph whose edges correspond to the identified (off-diagonal) entries of A (or B). When the required property holds, the corresponding directed graph is deterministic. Here, I identify several graph-theoretic conditions that are sufficient for a strongly connected directed graph to be deterministic, and I conjecture that one of them is necessary. These conditions naturally generalize the notion of chordality for undirected graphs, as chordal graphs are deterministic in the undirected case.

A nonnegative integer sequence pi=(d_1,\dots,d_n) is graphic if there exists a graph G such that pi is the degree sequence of G. In this case, we say that G is a realization of pi. We will begin by presenting several characterizations of graphic sequences, including the Havel-Hakimi algorithm and the Erdos-Gallai criteria.

Given a graph property P, such as connectivity or hamiltionicity, we say that a graphic sequence pi is potentially P-graphic if there is some realization of pi that has the property P. After reviewing several classical results, we will conclude with a discussion of some problems of more recent interest.

Given a graph H and a positive integer n, we wish to determine the minimum even integer m such that any n-term, graphic sequence pi, the sum of whose elements is at least m has a realization containing H as a subgraph. We denote this integer m by $\sigma(H,n)$. This value has been determined for several broad classes of graphs, which will be discussed here. If time permits, we will begin a discussion of some of the techniques used to solve problems of this type, which will be continued in the next seminar.

Note: Our speaker, Dr. Mike Ferrara, obtained his Ph.D. this summer from Emory University in Atlanta. He holds a post-doctoral position in the CU-Denver Math Dept and is working with Mike Jacobson.

I will begin by recalling the definitions of some classical (e.g., ovoid in 3-dimensional projective space) and some not-so-classical geometric objects (e.g., pseudo-ovals, pseudo-ovoids, unitals, SPG-reguli). Then I will introduce a new object called a semi-pseudo-ovoid, that generalizes the above mentioned objects. Restrictions on the parameters and characterizations of specific classes of semi-pseudo-ovoids will be given. As an application a new semipartial geometry will be constructed. This is based on joint work with J. A. Thas.

A graphic sequence Pi is said to be potentially H-graphic if there is some realization of Pi that contains H as a subgraph. After a brief review of the pertinent definitions, we will introduce a rather new technique in the field, the degree stripping method. The remainder of the talk will focus on determining sigma(H,n) using this technique for two graphs: the friendship graph F_k, which consists of k triangles meeting at a poknt, and K_s^t, the complete balanced t-partite graph. If time permits, there will be a brief discussion of possible future directions for this technique.

Cayley's Theorem says that the number of labeled trees on n vertices (i.e., the number of spanning trees in the complete graph K_n) is equal to n^(n-2). We will introduce some combinatorical techniques and use them to sketch some proofs of this theorem. If we don't give your favorite proof you will be invited to give a talk later in which you can explain it.

A tournament is an oriented complete graph. It is easy to show that every tournament contains a directed path that includes each vertex of the tournament, i.e., a hamiltonian path. Furthermore, every strongly connected tournament contains a hamiltonian cycle. In 1934, Redei showed that the number of distinct hamiltonian paths in a tournament T is always odd. Carsten Thomassen observed that not every odd number represents the number of distinct hamiltonian paths of a tournament by observing that no tournament contains exactly 7 hamiltonian paths. We show, with the aid of computers, that no tournament contains 21 distinct hamiltonian paths and conjecture that every other odd number is the number of distinct hamiltonian paths of some tournament. In the process, we develop an improved bound for the minimum number of hamiltonian paths in a strong tournament of order n. We also consider a conjecture of Grunbaum, which states that if a tournament of order n has k distinct hamiltonian cycles, then for every k' < k, there is a tournament of order n with k' distinct hamiltonian cycles. Easily shown to be false by a computer, we give an indirect argument that requires no computer search.

There are only two known ovoids in projective 3-space over a field of even characteristic. Over fields of odd characteristic it can be proved that there is only one type of ovoid. It has been long conjectured that the two known types in even characteristic are the only types that will exist, but we are still far from a proof of this very difficult conjecture. I will review what is known about these two types of ovoids and discuss an interesting way of going from one to the other.

We will introduce some classical problems in Ramsey Theory, then change gears and look at the following problem in graph Ramsey Theory. Given a graph H, we say that a graph G is ramsey for H if every 2-colouring of the edges of G yields a monochromatic copy of H. We say that G is ramsey-minimal for H if it is ramsey for H, but has no proper subgraphs that are. A graph H is ramsey-infinite if there is an infinite set of graphs that are ramsey-minimal for H. We look at a recent result which shows that the complete graphs are, in a sense, 'strongly' ramsey-infinite.

Interval Tournaments A directed graph is an interval digraph if to each vertex v there corresponds an ordered pair of intervals (S(v),T(v)) such that u beats v if and only if the intersection of S(u) and T(v) is nonempty. A tournament is an oriented complete graph. We characterize the tournaments that are interval digraphs via the existence of a large transitive subtournament and by forbidden subtournaments. A bipartite graph is an interval bigraph if to each vertex there corresponds an interval such that vertices are adjacent if and only if their corresponding intervals intersect and each vertex belongs to a different partite set. We capitalize on the equivalence of the models for interval digraphs and interval bigraphs and use results of Das, Roy, Sen, and West for interval digraphs, and results of Muller for interval bigraphs. We will also comment on some related open questions.

This is joint work with Dave Brown and Art Busch.

On Monday, 07 November 2005 there will be no meeting of the Discrete Math Seminar. Usualy attendees are invited to attend the MS presentation of Kate Bachman, which is advertised throughout the department and which starts at noon.

Let S=(P,B,I) be a finite generalized quadrangle (GQ) having order (s,t). Let p be a point of S. A whorl about p is a collineation of S fixing all the lines through p. An elation about p is a whorl that does not fix any point not collinear with p, or is the identity. If S has an elation group acting regularly on the set of points not collinear with p we say that S is an elation generalized quadrangle (EGQ) with base point p. S. E. Payne posed the following question: Can there be two non-isomorphic elation groups about the same point p? In this presentation, we show that there are exactly two (up to isomorphism) elation groups of the Hermitian surface in 3-dimensional projective space over the finite field GF(q), where q is a power of 2. Moreover, we investigate the possible EGQ's that can be constructed as a coset geometry of the new elation groups, and show that the EGQ we have constructed are isomorphic to the Hermitian surface.

Euler's constant, usually denoted by gamma, is defined by the limit of the sequence 1 + 1/2 + 1/3 + ...+ 1/n - ln(n).

The Riemann Zeta function Z(k) is defined as 1/1^k + 1/2^k + 1/3^k + ... .

Supose a worm (call it W) starts crawling on a 1 meter rubber band at 1 cm per minute while Stan Payne, at the other end, whose sole purpose in life is to frustrate W, stretches the rubber band 1 meter at the end of each minute. So, after 1 minute W is 1 cm from the start and 99 cm from the finish, then Stan stretches the band and (this is important) W maintains his relative position. So W is 2 cm from the starting point and 198 cm from the finish. Then W crawls another 1 cm in a minute and Stan stretches the band 1 m again. W is (after the stretching) 4.5 cm from the start and 295.5 cm from the finish. Does W ever reach Stan? Please assume infinite longevity for Stan and W, W is infinitely tiny, and the rubber band has infinite elasticity.

What does this have to do with Euler's constant and the Riemann Zeta Function? Come and see!

Let G = (V,E) be a simple graph, with S a subset of non-adjacent vertices in V. We say that S sparsely dominates G provided every vertex in V \ S has exactly one neighbor in S. In this talk we consider the task of sparsely dominating particular classes of regular and semi-regular graphs, some of which arise in the study of projective geometry.

This is joint work with Casey Trail, currently at Miami University (Oxford, Ohio).

PLEASE NOTE THE CHANGES IN TIME AND PLACE OF THIS SEMINAR (THERE IS A PRESENTATION AT NOON BY A CANDIDATE FOR THE POSITION IN COMPUTATIONAL MATHEMATICS)

Buekenhout has characterized as affine spaces the linear spaces that have the following two properties: (1) every plane is an affine plane, and (2) each line has at least 4 points. For generalized quadrangles (GQ) having order (q, q^2), Payne introduces a combinatorial Property (G). Pairs of collinear points may or may not have this property. In this talk, we will apply Buekenhout's theorem to a construction by Payne and Thas. This construction consists of certain points of the GQ(q, q^2) that are incident to the points of a pair having Property (G). In other words, we will find affine space lurking in the GQ. This talk will be self-contained for those knowing nothing of geometry.

An affine plane is a projective plane with a line of points removed. A (finite) translation plane is a type of affine plane that is constructed by starting with a rather special family of subspaces of a finite dimensional vector space over a finite field. This construction will be explained in detail. We have discovered a new class of planes that generalizes one found by Johnson, Pomareda and Wilke (J. Combin. Theory Ser. A 56 (1991), 272-284). More planes may be constructed from the ones found by replacing some of their lines with different point-sets that play the role of lines. This method gives two families of new planes that have also been studied.

The Ramsey Number R(m,n) is the smallest integer posessing the property that any graph of that order must contain either an s clique of order m or an independent set of order n. In his 1977 dissertation, Staton introduced the notion of Ramsey-type numbers in order to pose a simpler problem. The Ramsey-type number R_d(m,n) is the smallest integer with the property that any graph of that order and degree at most d must contain a clique of order m or an independent set of order n. He also calculated all numbers of the form R_3(3,m) by showing that the independence ratio of any triangle-free graph with maximum degree at most three must be at least 5/14. (The independence ratio of a graph is defined to be its independence divided by its order).

I will briefly cover the most important results pertaining to Ramsey-type numbers and independence ratios. Then I will present some of my research in which I have improved upon existing bounds for independence ratios for certain classes of graphs. Particular attention will be paid to Km-free graphs with maximum degree at most m.

I will survey Matou~Zek's 2003 book by the above name, including the applications to obtaining lower bounds for chromatic numbers of graphs, and proving nonembeddability of certain topological spaces in others (e.g., proving the non-planarity of graphs).

If D is a digraph, then the subset K of the vertices V(D) of D is a king set of D if D[K] is discrete and for each y in V(D) - K there is an x in K such that the directed distance from x to y is less than three. A king set K will be called minimal if no proper subset of K is a king set. We characterize both the digraphs which have a unique king set and those which have a unique minimal king set. We also give a sufficient condition for a digraph to have at least three minimal king sets.

Occasionally when trying to count the objects of a certain kind it turns out that the answer is given by the number of walks of a certain kind in a directed graph. When this is the case it is often possible to apply the so-called "Transfer Matrix Method." Sometimes this leads to a closed form formula for the answer, but often it merely leads to a nice generating function. Our goal in this talk is to introduce this method and then illustrate its use. For example, we will count the number f(n) of sequences a_1a_2...a_n where each a_i is 0,1, or 2 and with the property that a_1 = a_n and 0 and 2 are never next to each other.

The search for generalized quadrangles is an active area of research in which a structural property on pairs of points, called regularity, is often utilized. A point x is said to be regular if {x, y} is a regular pair for every other noncollinear point y. GQ's having every point regular are characterized by a construction from the symplectic group over a finite vector space V, this group being a subgroup of GL(V).

An outstanding question is: "Who are the other GQ's having a regular point?" We will report on computer searches for such a GQ that also has parameters s = t.

NOTE: THE DISCRETE MATH SEMINAR WILL NOT MEET ON MONDAY, 17 APRIL. THE TALK ORIGINALLY SCHEDULED FOR THAT DAY IS BEING POST PONED UNTIL THE FOLLOWING MONDAY.

We define the irregularity strength s(D) of a digraph D to be the minimum number s such that we can weight the arcs of D with integers i, 0 < 1 < s+1, such that the ordered pairs obtained by summing the inweights and outweights at each vertex are distinct. This extends the notion of graph irregularity strength which has been studied extensively. We determine the irregularity strength of directed paths, cycles, tournaments, and antipaths.

This is joint work with Mike Ferrara, Mike Jacobson and Thor Whalen.

Each March thousands of medical students put themselves at the mercy of a mathematical algorithm that will have a huge impact on the future of their medical career. We all probably know someone who has been on the waitlist for a kidney transplant. And certainly most of us have used mapquest, either to find the way to someone's house, or to take a long trip. We will take a look at the history of these problems and some of the graph theory used in solving them or attempting to solve them. In the first two cases we will see that the problems are easier to solve mathematically than in practice, and in the third case we will see that finding out what exactly is done is not so easy. Some of the presentation will be based on three excellent articles by Sara Robinson in the SIAM Newsletter. The medical matching problem is related to the Stable Marriage Problem, and a discussion of this with a local matchmaker led to the discrete modeling class developing an algorithm to help the matchmaker find best possible matches for her clients, and we will also discuss this.

A graph G is said to have thickness - t if E(G)can be partitioned into t and no fewer planar graphs. So for example, if G is planar, then G has thickness-one. For another example and with the help of Kuratowski's Theorem, it is easy to see that K_5 has thickness at least two. Exercise: Show that K_5 has thickness exactly two.

A longstanding open problem is the following: What is the largest chromatic number of any thickness-two graph?

Here is what is known so far: The largest chromatic number of any thickness-two graph is hmmm, where hmmm is one of 9,10, 11, or 12.

The "9" is due to exactly one example of a 9-critical thickness-two graph. The "12" is due to a straightforward argument that uses Euler's Formula.

I will talk about a new construction that produces infinitely many 9-critical thickness-two graphs, thus providing ballast to the "9." In addition I will introduce a new family of thickness-two graphs, the "permuted layer graphs" and talk about what is known so far abouot this new class of graphs. And finally, I will give an infinite family of non-trivial graphs for which both the thickness and chromatic number are known.

Many open questions will be provided at the end of the talk.

A graph G is said to be F-saturated if G does not contain a copy of F and for any edge e in the complement the graph G+e does contain a copy of F. The minimumsize of n-vertex F-saturated graphs, sat(n, F), is investigated. We give a history of the problem, present recent results (for when F is a cycle or a complete bipartite graph) and discuss many open problems.

Note: Because Monday, 4 September is a holiday, the Discrete Math Seminar will not be held that day. However, we have a visitor, Dr. John Schmitt, who will speak on Thursday during the usual "Proofs from the Book" seminar. Please note the change in time and place for the Discrete Math Seminar this week. ~

Reminder: John Schmitt from Middlebury College will speak at 1:00 p.m. on Thursday, 7 Sept. 06.

NOTE: The Discrete Math Seminar will not meet on September 11, 2006.

NOTE: On Sept. 18 Oscar Vega, Rich Lundgren and Mike Jacobson will each give 15 minute talks about their own research.

NOTICE TO ALL GRADUATE STUDENTS: The two Mondays Sept. 25 and Oct. 2 will be used to introduce graduate students to the research areas of the faculty members in discrete mathematics. On each of the two Mondays, each of our three speakers will give a fifteen minute introduction to his area of research. Please come and see what your professors are working on.

NOTICE TO ALL GRADUATE STUDENTS: The two Mondays Sept. 25 and Oct. 2 will be used to introduce graduate students to the research areas of the faculty members in discrete mathematics. On each of the two Mondays, each of our three speakers will give a fifteen minute introduction to his area of research. Please come and see what your professors are working on.

This is the first of a two-part presentation of an introduction to several basic topics in finite geometry (aka Galois geometry). Our goal is to proceed efficiently through the basic definitions and some of the proofs of pertinent theorems to reach (by the end of the second talk) a proof of the following theorem: If S is a symplectic spread of PG(3,2^e) that contains even one regulus, then S must be regular spread. This is a significant result in finite geometry with several applications. A basic understanding of vector spaces over a field along with a willingness to imagine that the field could be finite are the only prerequisites for these two lectures. Lecture notes will be available.

This is the second of a two-part presentation of several topics from finite geometry (aka Galois Geometry). The goal is to introduce ideas and techniques used to prove the following theorem: Any symplectic spread of PG(3,2^e) that contains even one regulus must in fact be a regular spread. These two talks could be considered an introduction to finite geometry. Lecture notes will be provided.

Abstract: Domination graphs arose from the study of tournaments. Two players u and v are said to dominate in a tournament if for every other player w, either u beats w or v beats w. In general, the digraph does not have to be a tournament. Vertices u and v dominate if for every other vertex w, (u,w) or (v,w) is an arc in D. Given a digraph D=(V,A), the domination graph of D, dom(D), is the graph with vertex set V and an edge between every pair of dominating vertices.

A large cadre of researchers in this area has passed through the halls of CU-Denver. In this pass, we will explore digraphs with isomorphic underlying graphs, UG(D), and domination graphs. The case where the two are equal has been completely characterized. Classes of digraphs where UG(D) is isomorphic but not equal to dom(D) have been found, although this portion of the problem has not, as yet, been fully characterized. This talk is based upon work done with Larry J. Langley of University of the Pacific.

Spectators are encouraged to bring writing utensils. There may be an opportunity to participate.

You teach calculus and you want to create an exam question with a cubic polynomial having integer coefficients, distinct integral roots, and integral critical values. Can you do it?

Try it now!

If you want to see a complete determination of all such polynomials, come to the Discrete Math Seminar.

A strongly regular graph with parameters (v,k, lambda, mu) is a k-regular graph on v vertices with the property that every pair of adjacent vertices have lambda common neighbors, and every pair of nonadjacent vertices have mu common neighbors. A partial difference set is a subset of a group, the existence of which is equivalent to the existence of a stgrongly regular Cayley graph on that group. We will review some basic results and constructions, concentrating on those which arise in Galois Geometries. Our main result is a proof of the nonexistence of abelian partial difference sets with parameters (p^2(p+2)^2, p(p+1)^2, p, p^2+p), where p and p+2 are both prime. Along the way, we prove a curious lemma on matchings in bipartite graphs.

Abstract:The classification of the finite simple groups is unprecedented in the history of mathematics, for its proof is 15,000 pages long, representing the combined effort of more than 100 mathematicians in over 500 articles published between the late 1940's and the early 1980's. While common knowledge has it that the proof was completed in the early 80's, several gaps were found, one of them serious, and only recently in an article in the AMS Notices has Michael Aschbacher stated that he once again believes that it is a theorem. In this talk we will mention briefly the ultimate result, but will focus more on the long history leading up to the final classification. We will start with Galois in the 1830's and his use of a simple group to prove the insolvability of the quintic, and then discuss the work of Sylow and Burnside. The range problem began around the turn of the century, and we will trace it to the 70's and Marshall Hall's paper on the simple groups of order less than 1,000,000. We will discuss Brauer's pioneering work in the 50's followed by Thompson's odd order and N-groups papers. And of course we will discuss Janko's remarkable discovery of a new sporadic simple group in 1966, the first in 100 years, and an event that sparked an exciting 10 year period when some 21 new sporadic simple groups were discovered. And finally we will look at the work of Daniel Gorenstein, the commander-in-chief or quarterback of the final assault on the problem. I was fortunate to be one of those 100 contributers during perhaps the most exciting period, 1967-1975, and was also fortunate to be a student of Janko. So I will also share some experiences from those years that did not make it into the journals but shed some light on some of the leading characters in the final proof. For the most part, this will not be too technical a talk, so it should be of interest to a diverse mathematic's audience.

Hilbert's Nullstellensatz states that if F is an algebraically closed field and f, g_1, ... g_m are polynomials in the ring of polynomials in n variables over F, where f vanishes over all common zeros of the g_i's, then there is an interger k and polynomials, h_1, ..., h_m in the ring so that f^k is equal to the sum of the h_ig_i. In the next two seminars we will prove a stronger result for the case m=n and each g_i univariate. We will then give applications of the result in several areas, including Combinatorial Number Theory, Graph Theory and Combinatorics.

This is a continuation of last week's presentation by Angela Harris.

Hilbert's Nullstellensatz states that if F is an algebraically closed field and f, g_1, ... g_m are polynomials in the ring of polynomials in n variables over F, where f vanishes over all common zeros of the g_i's, then there is an interger k and polynomials, h_1, ..., h_m in the ring so that f^k is equal to the sum of the h_ig_i. We will prove a stronger result for the case m=n and each g_i univariate. We will then give applications of the result in several areas, including Combinatorial Number Theory, Graph Theory and Combinatorics.

The students attending the Combinatorics Seminar have chosen the Theory of Matroids as the main subject of study for the Spring 2007 semester. At the first meeting of the Discrete Math Seminar an introduction to the general area will be presented as an invitation to participate in the Combinatorics Seminar.

A paper by H. Whitney in 1935 is generally credited with having been the first to abstract the notion of linear dependence in a way that covers all sorts of situations that arise in disparate areas of mathematics. A major outgrowth of that paper is the theory of matroids, the most general common context in which the greedy algorithm is effective. A major characteristic of matroid theory is the rather large (certainly more than fifty) number of different approaches to the subject. We start with a description in terms of independent sets, use this to explain the greedy algorithm, and then begin the study of some of the cryptomorphic versions.

Probably one of the hottest areas in current mathematics is the study of knots and links, as several links (pun intended) have been found between invariants of these objects and other areas of mathematics.

I will introduce the study of knots and links from a combinatorial point of view. Most of the results presented will belong to the world of polynomial invariants, which are currently studied as graded co-homologies of certain modules over polynomial rings.

Special attention will be given to Jones, and Kauffman polynomials.

----------------------------------------------------------

If a is an integer and p a prime, we say that a is a quadratic residue modulo p if a is congruent (modulo p) to b^2, for some integer b. This concept gives rise to the Legendre symbol (a | p) which is defined as: (a | p)=0 when gcd(a,p)>1, (a | p)=1 when a is a quadratic residue modulo p, and (a | p)=-1 when a is not a quadratic residue modulo p. The Legendre symbol, which gives rise to a multiplicative character on the integers modulo p, is then extended to all integers by the Jacobi symbol and the Kronecker symbol. In this talk, we discuss the paper Quadratic Reciprocity in a Finite Group, by William Duke and Kimberly Hopkins. In this paper, via character theory and algebraic number theory, the authors extend the law of quadratic reciprocity to finite groups so that, if G is a group and a any integer, there is a value for the symbol (a | G). In this talk we briefly discuss necessary background material, sketch a proof of their result, and provide some concrete examples such as when G is abelian or when G is one of the simple groups SL(2,q).

We will review some results on symplectic planes that are formed by isotropic subspaces of a given symplectic form on a 4-dimensional vector space.

Most of the talk will be on (known) geometric properties of these planes and the type of symmetries they admit. Also, some work (in progress) dealing with ovoids in PG(3,q), q even, that contain one translation oval will be discussed.

No previous knowledge of translation planes or symplectic forms will be assumed. This talk should be accessible to anybody who has taken a linear algebra course and knows what a group action is.

Another talk with deeper and more technical results on this material will take place Friday February 23, 2007 at the Rocky Mountain Algebraic Combinatorics Seminar at CSU, Fort Collins.

---------------------------------------------------------------------

Let H be a graph. The extremal (or Turan) number of H, denoted ex(n,H) is the minimum number of edges needed to assure that every graph G with n vertices and at least ex(n,H) edges contains H as a subgraph. Often, the problem of determining ex(n,H) is called the Turan problem. In this talk, we will discuss two variations of this classic extremal problem: Potentially H-graphic sequences and H-saturated graphs of minimum size.

The parameter s(H,n) is defined to be the smallest even integer m such that every n-term graphic degree sequence with degree sum at least m has some realization that contains H as a subgraph. We will discuss two techniques to determine s(H,n) in the case where H is an arbitrary union of disjoint cliques. We will also give a lower bound on s(H,n) for arbitrary H. We are currently unaware of any result in the literature for which this bound is not sharp.

A graph G is H-saturated if G does not contain H as a subgraph but, for any nonadjacent vertices u and v, G+uv contains H as a subgraph. The parameter sat(H,n) is defined as the minimum number of edges in an H-saturated graph of order n. The number of graphs H for which sat(H,n) is known exactly is quite small. We determine sat(H,n) when H is a union of cliques of the same order, an arbitrary union of two cliques and a generalized friendship graph. We will also give a conjecture relating the parameters sat(H,n) and s(H,n).

Let D(n) be the determinant of the n by n matrix with each diagonal entry equal to a, with each entry just above or just below the main diagonal equal to b, and with all other entries equal to 0. We will guide the audience to find a formula for D(n)in two different ways, illustrating two standard methods of evaluating combinatorial problems: the first using generating functions, the second using recursion and guessing.

NOTE: The Discrete Math Seminar will not meet either March 12 or March 19. Our next speaker will be Chuck Cabel on March 26.

A king set K of a digraph D is a subset of V(D)satisfying two properties: (i) Ruling Property: If y is in V(D)\K, then there is an x in K such that the directed distance in D from x to y is either 1 or 2;

(ii) Royal Courtesy Property: No two vertices of K are adjacent.

In an earlier talk (in this seminar) we showed how to find the number of king sets of a labeled oriented cycle. In this talk we show that the number of king sets of a labeled oriented wheel whose center is not a source is greater than or equal to the number of king sets of its rim (a labeled oriented cycle). We will show how this is proved for a certain class of wheels and then give an outline of how the proof goes for all remaining labeled oriented wheels.

A (k, g)-cage is a graph having valency k and girth g, but with minimum order of vertex set. Cages have a high degree of symmetry, and probably due to this fact, they make occasional appearances in different areas of math and the sciences. Although cages were first introduced in 1947 by Tutte, today their structure remains largely unknown. An open conjecture of Fu, Huang and Rodger is that a (k, g)-cage must be k-connected; and in fact, they proved this is the case for k = 2. Daven and Rodger, and independently, Jiang and Mubayi, have shown this conjecture also to be true for the case of k = 3. This talk is introductory and well-suited for first-year graduate students.

The celebrated secretary problem (known also as the best choice problem) was introduced almost 50 years ago and can be stated as follows: There are n candidates for a secretary position that are linearly ordered, or ranked, from the worst to the best. They are observed one by one in some random permutation by a selector who is stopping the interview process at some moment and picking the presently examined candidate. The choice of the selector is based only on the relative ranks of the candidates examined so far and the number n of candidates. He has no knowledge of the ranks of future candidates. The objective is to maximize the probability of selecting the best candidate.

This problem was solved by Gilbert and Mosteller in 1966. Since then many variants, enrichments and generalizations of the classical versions were examined. All of them required either the linear order or at least some partial order on the set of all candidates. In 2005 Kubicki and Morayne published the first paper in which no order structure was required. That paper has opened a new venue of research in this well-established area. We define a formal model of an optimal stopping problem on graphs and directed graphs. The only structure of a set under consideration is a graph's (or digraph's) adjacency relation, that need not to be transitive. We specify some aim set, a subset of vertices of the graph, and want to maximize the probability of stopping at an element of this aim set.

Two cases of this graph-theoretic model have been solved and will be discussed: directed paths with aim set equal to the maximal element was solved in 2005 and complete unbalanced bipartite graphs with the aim set being the smaller partite set was recently solved by Kubicka and Kubicki.

In this talk I will present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. The constructions were motivated by coordinatizations of some well known finite geometries. The graphs in all such families possess some general properties including regularity or bi-regularity, existence of special vertex colorings, and existence of covering maps between every two members of the same family (hence, embedded spectra). Another general property is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans.

A bipartite version of these graphs is defined as follows. Let R be a commutative ring (in many applications R= GF(q)). Let f_i: R^{2i-2}\to R be an arbitrary function, i > 1. We define the bipartite graph B\Gamma_n = B\Gamma (R;f_2,\ldots, f_n) as follows. The set of vertices V(B\Gamma_n) is the disjoint union of two copies of R^n, one denoted by P_n and the other by L_n. We define edges of B\Gamma_n by declaring point (p)=(p_1,p_2,\ldots,p_n) and line [l]=[l_1,l_2,\ldots,l_n] to be adjacent if and only if an explicitly given set of n-1 relations on their coordinates hold.

In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems which deal with cycles in graphs. I will explain motivations for these constructions, survey both old and new related results, applications, and state some open questions.

Abstract: H-decompositions of graphs have a long history that has spanned at least 40 years. An H-decomposition of a graph G is a partition of the edge set of the graph G into isomorphic copies of H. If an H-decomposition of a graph G exists, we sometimes write H | G. We introduce the problem of gracefully labeling trees, that is numbering the vertices of a tree T_n with n labels so that the values of the absolute values of the end-vertices of every edge of the tree are all distinct. We show that if T_n+1 has a graceful labeling, then K_2n+1, the complete graph on 2n+1 vertices has a T_n-decomposition. We will also show that if H_n is a graph of size n, then H_n | K_2n+1.

In classical projective geometry, a double-6 of lines consists of 12 lines l_{1},l_{1}, ... , l_{6}, m_{1}, m_{2}, ... , m_{6} such that l_{i} meets m_{j} if and only if i /= j. In the 1960's Hirschfeld studied this configuration in finite projective spaces, showing they exist except for some some exceptions over GF(q) when q is small. We will be considering double-k sets in the symplectic geometry W(q), which is constructed from PG(3,q) using an alternating bilinear form. This geometry has the nice property that if we take a line l, and a point P not on l, then there is exactly one line through P meeting l. We will discuss all of this in detail, including all of the basic definitions needed to understand the problem, and give a result classifying which values of k and q allow us to construct a double-k set in W(q).

A spanning cycle in a graph G is called a hamiltonian cycle and if such a cycle exists, we say that G is hamiltonian. For a subgraph H of G we say that G is H-avoiding hamiltonian if there is a hamiltonian cycle in G that contains no edges of H or, in other words, if G \ E(H) is hamiltonian. In this talk we will discuss some new results on H-avoiding hamiltonian graphs. In particular we will consider the case where H is a hamiltonian cycle, which will lead to a discussion of extending families of edge-disjoint hamiltoinian cycles.

A Latin square of order n is an n by n array using n symbols, such that each symbol appears exactly once in each row and in each column. A set of Latin squares is said to be mutually orthogonal provided that for each pair in the set, if we superimpose the squares, each two of the n squared ordered pairs are distinct. A popular puzzle called Sudoku involves Latin squares where n = 9, along with the added condition that that each of the nine symbols also appears exactly once in each of the 3 by 3 blocks that together tile the main array. In response to a question posed in the American Mathematical Monthly, we provide a construction for mutually orthogonal Latin squares (MOLS) that are solutions to the Sudoku puzzles as well. We also generalize this notion from n = 9 to n = k^{2} and construct mutually orthogonal Sudoku Latin squares (MOSLS) for any integer k > 1.

Hall planes, which are obtained from Desarguesian planes by a process known as derivation, are, in many respects, the most "Desargues-like" of the nondesarguesian projective planes. Many questions concerning Hall planes can be answered by considering the issues in the corresponding Desarguesian plane and then tracing through the derivation process which gives the Hall plane. On such question concerns the existence of ovals in Hall planes. The known results come from "inherited arcs", that is, point sets which are arcs in the Desarguesian plane and remain arcs after the derivation process. I will show how these results can all be combined and extended. Moreover, there exist hyperovals in Hall planes of even order which do not arise this way and I shall describe their construction. These results account for all the hyperovals in the Hall plane of order 16 which were determined by exhaustive computer searches.

An n digit number t is Nivenmorphic if there exists a number N with the following properties: 1.N is a multiple of t.

2.The digital sum of N is t.

3.The last n digits of N are t.

First, we will prove 2 propositions directly related to digital sums. These will allow a straight forward proof that every number greater than 20 is Nivenmorphic. Then we will prove that the integer 11 can't possibly be Nivenmorphic.

Let p be an odd prime and q=p^e. Beginning with an ovoid in PG(3,q), we remove points to form a particular (q^2-1)/2-cap O ' (a set of points no three of which are collinear) and ask what is the number, N, of points of O' lying on the various planes of PG(3,q). Extensive numerical evidence shows that

(q+1)/2-\sqrt{q} -1 < N < (q+1)/2} +\sqrt{q} +1

for all prime powers q < 100. We show that the plane-intersection problem is equivalent to finding the number of points in the intersection of two specific quadratic cones in PG(3,q). The cone intersection problem is shown in turn to be equivalent to the problem of finding the number of points on a particular plane curve of degree 4. Under a suitable transformation, this curve is shown to satisfy the hypotheses of the theorem of Hasse and Weil, which gives bounds on the number of points on an algebraic curve. This shows that the bounds given above are always satisfied.

We start by proving an 1878 theorem of E. Lucas and then use it to reformulate a problem of R. Graham, for the solution of which he has offered $250. Graham asks for a proof that there are infinitely many positive integers n for which the number of combinations of 2n things taken n at a time is not divisible by 3 or 5 or 7. We also mention a few other open problems from elementary number theory.

In 1899 Georg Pick proved the following beautiful theorem: A point of the Euclidean plane E coordinatized in the usual fashion is said to be a lattice point provided both its coordinates are integers. Let P be a simple polygon in E (i.e., its boundary does not cross itself) such that each of its vertices ia a lattice point. Let I be the number of lattice points in the interior of P and let B be the number of lattice points on the boundary of P. Then I + B/2 - 1 is the area of P. We give the "Proof From The Book" of Pick's theorem, starting with a proof of Euler's formula for planar graphs.

The RSA Public Key Code uses elementary number theory to make it possible for Alice (or anyone else with the necessary but publicly available information) to send Bob an encoded message which only Bob knows how to decode. We will explain the number theory needed and then give a detailed description of this scheme.

Strongly regular graphs, introduced by Bose in 1963, form a combinatorial model for permutation groups of rank 3 (that is, permuation groups with 3 orbits on ordered pairs) and even order. These groups have been completely classified, using the classification of finite simple groups. They come in three kinds, one of which - the affine - was the last to be dealt with in a paper of Liebeck from 1987. However, strongly regular graphs are far from being classified. They come with four parameters : the number of vertices, the valency, the number of common neighbors to a pair of adjacent vertices and the number of common neighbors to a pair of non-adjacent vertices. (Indeed, the definition is just that these four numbers be constants.)

Here I wish to consider the analog for strongly regular graphs of the affine permutation groups of rank 3, where the vertices are the vectors of a vector space and two vertices are joined if and only if the span of their difference lies in a set X of points of the corresponding projective space. That the graph is strongly regular turns out to be equivalent to the condition that X has two intersection sizes with hyperplanes. Thus objects heavily studied by finite geometers, such as hyperovals, unitals, ovoids, maximal arcs give rise to strongly regular graphs.

An infinite family of (affine) strongly regular graphs with new parameters will be constructed by constructing a set of points in the projective plane over a field of odd, square order with two intersection sizes with lines. These sets are in some sense the odd order analog of the maximal arcs of Denniston from 1969 (although they are not maximal arcs, as guranteed by a theorem of Ball, Blokhuis and Mazzocca from 1997). Rather the analogy is via the symmetries of the sets. The construction uses a pencil of conics in the plane.

P.S. The usual refreshments will be available.

A tournament is a digraph (directed graph) resulting from orienting the edges of a complete graph. The score of a vertex is the number of vertices that are dominated by that vertex. If an n-tournament T has vertices v1, v2, . . . . , vn , with si the score of vi, 1 <= i <= n , so that 0 <= s1 <= s2 <= . . . <= sn , then the sequence (s1, s2, . . . , sn) is called the score sequence of T. Landau proved that a sequence of non-decreasing integers, (s1, s2, . . . , sn), is a score sequence of some n-tournament if and only if the sum of the first k terms is greater than or equal to k choose 2 for all k from 1 to n, with equality when k=n. We will look at two proofs of this theorem.

Recently tournaments that are interval digraphs have been characterized by Brown, Busch, and Lundgren. They show that a tournament on n vertices is an interval digraph if and only if it has a transitive (n-1)-subtournament. We investigate a broader class of oriented graphs on n vertices that contain a transitive (n-2)-tournament as a subdigraph. If such an oriented graph D is not itself a tournament, then it may be an interval digraph even if it does not contain an (n-1)-transitive tournament as a subdigraph. A directed graph D is an interval digraph if for each vertex u there corresponds an ordered pair of intervals (S(u), T(u)) such that uv is an arc of D if and only if the intersection of S(u) and S(v) is nonempty. A bipartite graph G is an interval bigraph if to each vertex there corresponds an interval such that vertices are adjacent if and only if their corresponding intervals intersect and each vertex belongs to a different partite set. We use the equivalence of the models for interval digraphs and interval bigraphs in our investigation of which of these oriented graphs are interval digraphs. This is joint work with Shilpa Das Gupta and Elena Ortega.

A graph G is said to be hamiltonian if it contains a spanning cycle. Given a hamiltonian graph G, we study the existence of cycles of various lengths in G given the existence of a pair of vertices that have a high degree sum.

NOTE: The Discrete Math Seminar will not meet on 4 February. The talk by Angela Harris will be given on 11 February instead.

A useful theorem in the book Linear Groups by L. E. Dickson gives the number of solutions (x,y) to the equation ax^2 + by^2 = k for nonzero elements a,b,k in the Galois field of order q. We show that the theorem my be proved using well­known properties of nondegenerate quadrics in PG(3,q)

What is the nature of mathematical knowledge for secondary teaching? International researchers agree that secondary mathematics teacher preparation must address the procedural, rule-bound nature of prospective teachers' understanding of many secondary mathematics topics. No longer is it assumed that advanced university-level mathematics coursework is adequate preparation to teach secondary mathematics. Aspiring teachers majoring in mathematics often must de-construct and re-construct their rule-bound understanding of familiar school mathematics topics into a more dynamic and penetrating understanding of concepts, algorithms, methods of inquiry, and disciplinary perspectives. The challenge for teacher educators is to engage prospective teachers in reflection, critical analysis, and penetrating discussion about school mathematics topics that they think they already know. Video cases of K-12 students’ thinking are known to stimulate provocative mathematical discussions among teachers. In this talk, I propose manipulative modeling tasks as another knowledge-eliciting and knowledge-developing cognitive tool for mathematics teacher preparation programs. The tasks reported in this talk focus on non-Euclidean geometry, algebra, and integers.

In a projective plane of order n, a set of n+1 points no three collinear is called an oval. When n is even, the oval can be uniquely extended to a set of n+2 points no three collinear called a hyperoval. Ovals and hyperovals have applications in coding theory and their classification remains a large open problem in projective geometry. We will discuss the current progress that has been made on this problem, focusing on two specific questions. First the problem of classifying ovals in planes called Hall planes of odd order will be discussed, followed by a discussion concerning the work towards a generalization of a hyperoval known as the O'Keefe-Penttila hyperoval. Several approaches to this last problem will be presented, including a geometric/algebraic approach, a combinatorial optimization approach, and an approach that views hyperoval as eigenvectors of a matrix. No previous knowledge of projective geometry will be assumed.

A useful theorem in the book Linear Groups by L. E. Dickson gives the number of solutions (x,y) to the equation ax^2 + by^2 = k for nonzero elements a,b,k in the Galois field of order q. We show that the theorem my be proved using well­known properties of nondegenerate quadrics in PG(3,q)

Professor Thas is known internationally as one of the foremost experts on finite geometries. His talk will be designed for a general audience in discrete mathematics.

Refreshments will be served just prior to the talk.

It is well known that each finite abelian group may be written as a direct product of cyclic groups, and this fact is proved in many beginning abstract algebra texts and in elementary group theory texts. It seems natural, then, to ask what the automorphisms of such a group are. However, we have not been able to find a complete treatment of this topic in any abstract algebra or group theory text. Hence it was with special pleasure that we discovered a recent article by C.J. Hillar and D. L. Rhea in the American Mathematical Monthly [14(2007), 917 -- 923] that presents a succinct (but basically complete) treatment of this problem. This talk will be an exposition of this paper.

If D is a digraph, then a subset K of V(D) is a king set of D if D[K] is discrete and for each y in V, there exists an x in K such that the directed distance from x to y is less than 3. We give characterizations of those digraphs having a unique king set, those having exactly 2 king sets and those having at least 3 king sets.

The extremal number of a simple graph G and an integer n is the largest number e such that there is a graph on n vertices with e edges, no subgraph isomorphic to G, and the property that the addition of any edge results in a subgraph isomorphic to G. The saturation number of G and n is the smallest such e. We'll discuss some known extremal and saturation numbers, extend the definition of saturation to directed graphs, and see a few results.

An irregular digraph is a digraph whose vertex degree pairs are all distinct. Irregular digraphs and irregular multi-digraphs have a very nice property that they have an error-correcting degree matrix. We aim to introduce a new term into the graph theorist's dictionary.

Define a pair of maps f,g where f is from the arc set of a digraph into the positive integers and g is defined by

g(v)=(\Sum_{vx in A(D)} f(vx), \Sum_{xv in A(D)} f(xv)).

If all the degree weights (g(v)) are distinct across V(D), then we say f is an irregular arc labeling of D. Let I(D) be the set of irregular labelings of D. If s is the maximum value for f(e) for e in A(D), we say f is an irregular s-labeling and g is an irregular s-weighting if f and g satisfy the above conditions. The irregularity strength of a digraph D is the minimum such s used for f in I(D).

We give various techniques for determining digraph irregularity strength and constructing irregular labelings of digraphs using the minimum possible maximum value as a label. In particular, if we know that s is the irregularity strength of D, then we write s(D)=s.

We develop the topic of an irregular orientation of a graph G. We show that the class of graphs that have at most 2 vertices of any given degree have irregular orientations.

Abstract: Recently tournaments that are interval digraphs have been characterized by Brown, Busch, and Lundgren. They show that a tournament on n vertices is an interval digraph if and only if it has a transitive (n - 1)-subtournament. If such an oriented graph D is not itself a tournament, then it may be an interval digraph even if it does not contain a transitive (n - 1)-subtournament as a subdigraph, as long as there are specific restrictions on D. We explore what restrictions we can place on D to guarantee that it is interval, and in particular we investigate a broader class of oriented graphs on n vertices that contain a transitive (n - 2)-tournament as a subdigraph. A directed graph D is an interval digraph if for each vertex u there corresponds an ordered pair of intervals (S(u), T(u)) such that uv is an arc of D if and only if the intersection of S(u) and S(v) is nonempty. A bipartite graph G is an interval bigraph if to each vertex there corresponds an interval such that vertices are adjacent if and only if their corresponding intervals intersect and each vertex belongs to a different partite set. We use the equivalence of the models for interval digraphs and interval bigraphs in our investigation of which of these oriented graphs are interval digraphs.

A digraph is an interval digraph if to each vertex v there is ordered pair of intervals of the real line (Sv , Tv ), such that if u beats v, Su intersects Tv nontrivially. A bipartite graph with vertex partition X U Y is an interval bigraph if to each vertex v ? XUY there corresponds an interval of the real line such that the vertices x ? X and y ? Y are adjacent if and only if the x interval and the y interval intersect nontrivially. An interval digraph can be made into an interval bigraph by creating a vertex for both the Sv and Tv interval. A tournament is a complete oriented graph. A graph H is called a circular arc graph if it is the intersection graph of a family of arcs of a circle. Recently, interval tournaments have been characterized completely. In looking for the circular arc representation for the compliment of the bigraphs created from interval tournaments, we found an interesting class of circular arc graphs. This led to a broader class of interval graphs, which includes interval tournaments.

A unital is a 2-(q^3+1, q+1, 1)-design. Of special interest are those unitals that can be embedded in a projective plane. A unital U in a projective plane P of order q^2 can be defined as a set U of q^3 + 1 points such that each line of P intersects U in either 1 or q+1 points. The classical example is given by the point set of a Hermitian curve in PG(2,q^2). It has a 2-transitive automorphism group.

In this talk I will first present the known results concerning unitals with a transitive automorphism group. They basically are all of the following form: "Given a unital admitting a transitive automorphism group in a projective pland and satisfying some extra condition, then the unital is a Hermitian curve in PG(2,q^2)." Then I will present a new result on transitive unitals in PG(2,q^2).

A graph G is a probe interval graph if there is a collection of real-line intervals in correspondence with the vertices of G and the vertices are partitioned into sets P and N such that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. A probe interval graph can be though of as a graph embedded in an interval graph such that the set of vertices belonging to N are not adjacent. I will present some recent results in the theory of probe interval graphs and some directions for research on them, including the investigation of applying lexicographic breadth first search to recognize certain subclasses of probe interval graphs. An overview of the utility of lexicographic breadth first search will be given, as will an introduction to the algorithm itself.

One way to construct nondesarguesian projective planes is to start with a standard field plane and redefine some of the lines (while leaving the points alone) in such a way that the final result is still a projective plane. One of the easiest such construct leads to the Hall planes. In this situation, a natural question to ask is whether a given set of points having some special property in the field plane retain this property after the lines have been redefined. When this occurs, we say that the point set is inherited in the new plane.

I will describe the details of such a construction, producing a Hall plane of even order, and examine the hyperconics which could be inherited in these Hall planes. This work finishes a classification of the inherited hyperconics that was started in 1996 by O'Keefe and Pascasio.

The concept of a cycle is a concept that appears in both graph theory and in group theory. In particular, every element of a permutation group can be written as a product of disjoint cycles. If a group acts as automorphisms on a graph, it is interesting to consider what happens when a cycle in the graph appears in the same order as a cycle in a group element. We discuss several nice results under which transitivity of the automorphism group guarantees an easy count on the number of orbits of cycles that appear in both the group and the graph under the action of the automorphism group. This talk is based on a paper by Bill Kantor in the June-July edition of the American Mathematical Monthly.

Recall that an affine plane is a linear space satisfying the following condition, sometimes referred to as Playfair’s Postulate, “Given a line, l, and a point, p, not on l, there exists a unique line, m, through p, parallel to l.” Playfair’s Postulate is a variation on Euclid’s fifth postulate, and in this sense, affine planes are generalizations of the Euclidean plane. With this motivation we consider the following definition giving a further generalization.

Let P and L be (not necessarily distinct) sets. Let I be a relation on P x L and let IC be the complement of I in P x L. Let J be a relation on L x L. We say S = (P, L, I, J) is a Generalized Playfair Structure provided the following condition, called the GPS Axiom, holds: “Given any (p, l) in IC, there exists a unique m in L such that (p, m) is in I and (l, m) is in J.”

In this talk we consider various algebraic/combinatorial structures satisfying the GPS Axiom. We also consider a class of graphs which arise naturally from these structures.

A graph of order n is hamiltonian if it contains a cycle of length n, and is said to be pancyclic if it contains cycles of all lengths from three to n. Let G be a graph and H be a subgraph of G. If G contains a hamiltonian cycle C such that no edge in C is contained in H, we say that C is an H-avoiding hamiltonian cycle. Let F be any graph. If G contains an H-avoiding hamiltonian cycle for every subgraph H of G such that H is isomorphic to F, then we say that G is F-avoiding hamiltonian.

In this talk we will discuss the existence of cycles of various lengths in a hamiltonian graph G given the existence of a pair of vertices that have a high degree sum on a hamiltonian cycle in G. We will also give minimum degree and degree-sum conditions which assure that a graph G is F-avoiding hamiltonian for various choices of F.

Many cryptographic systems have their security based on the difficulty of either factoring large integers, or of solving for discrete logarithms. Thus evaluating the difficulty of these two types of problems is of much interest to cryptanalysts. There have been several recent advances in the methods used to factor integers, most notably the elliptic curve method, which is a modification of the Pollard-Rho (p-1) factoring algorithm, and the number field sieve method, a modification of a method known simply as the rational sieve. The number field sieve is especially useful for factoring integers that have very large prime factors, and so is of special importance in evaluating the security of RSA systems.

The number field sieve relies on a significant amount of algebraic number theory. In this talk, we will discuss some of the classical factoring algorithms, and then we will look into some of the number- theoretic ideas behind the number field sieve. We will then describe this algorithm, and conclude with a comparison of some of the more modern factoring techniques.

This is a reminder that the Discrete Math Seminar will not meet today. Please come to the Social on Friday, 17 October. Pizza at noon and a talk by Travis Kowalski, South Dakota School of Mines and Technology, at 1:00 p.m.

Warning: I do not have a speaker for October 20. Please volunteer! S.E.P.

No Meeting Today! We need speakers! At the present time we have tentatively scheduled speakers on

November 17, December 1 and January 26.

Stan

The Kronecker product of two matrices (i.e., their tensor product) will be defined and several basic properties will be developed. Application to the construction of Hadamard matrices (and their related (v,k,lamda)-designs) will then be easy. The Vec operator on matrices will be developed and used along with the Kronecker product to show how to solve matrix equations of the form AXB = C, where A, B, C are given matrices of appropriate sizes and X is the unknown matrix being sought.

Please note the date.

A Moufang loop L is the generalization of a group that arises when the associative law is replaced by any one of the Moufang identities:

(xy)(zx) = x((yz)x); ((xy)x)z = x(y(xz)); ((zx)y)x = z(x(yx))

for all x, y, z in L. In this talk we will define what it means for a group to admit triality. From there we will focus on Latin Square Designs to see the connections between Moufang loops and groups with triality. By seeing the correspondence between triality groups and Moufang loops one can get a better understanding of why Moufang loops behave like groups. In this talk we will also expand upon some of the recent results (Lagrange's Theorem & Sylow's Theorems) that have beenachieved using triality groups.

Classroom voting allows us to move away from lecture and towards a student-centered, interactive classroom. Rather than just telling the students about mathematics, it is possible to ask questions that will draw the knowledge out of the students and engage them in vibrant discussions. This method has been used in courses ranging from college algebra to abstract algebra, and everything in between. We will give examples from several courses, as well as discuss some studies of effectiveness and strategies for using this powerful technique in your own classes.

NOTE: THIS WILL BE OUR LAST DISCRETE MATH SEMINAR THIS SEMESTER

In our first course on linear algebra, we learn to solve systems of linear equations. For example, how to find all points in space that satisfy both of the equations (A) x + y + z = 0 and

(B) x − 2y + z = 0.

The geometry of this problem is simple. The points that solve (A) form a plane, the solution set for (B) is a different plane, and the set of common solutions is their intersection, which is a line. The difficulty of solving such systems does not signif- icantly depend on the number of variables or the number of equations. However, equations that involve higher powers of the variables, say x^2 or the product xyz , are surprisingly complicated, and it is a fundamental goal to understand the geometry of their solution sets, which are called algebraic varieties.

It is a general principle in mathematics to study an ob ject via functions de- fined on it. Families of functions defined on varieties form commutative rings, and it is a firmly established maxim that understanding a ring is tantamount to understanding its module category.

Over small rings, notably finite dimensional algebras over a field, it is sometimes possible to give an exhaustive description of the module category by classifying its indecomposable ob jects. When this is not possible, one hopes to find characteristics of the ring—and the corresponding variety—reflected in a manageable subcategory of its modules category. Striking examples of such connections emerged in the 1980s; in the talk I will survey these results and recent improvements.

Farhad Shahroki introduced two classes of partially ordered sets, which are defined using specific straight line segments in the Euclidean plane. Both classes are natural generalizations of interval containment orders and interval orders. We prove several properties of the classes, and---inspired by the observation that the classes seem to be very similar---we focus on the question whether they are distinct. The study of these classes is in part motivated by the Removable Pair Conjecture: every poset with at least 3 vertices contains a pair, whose removal does not decrease the dimension by more than one.

This is joint work with William T. Trotter.

Broadly, structural graph theory is concerned with ensuring, or prohibiting, the presence of certain substructures within a graph. The most prevalent results of this type in the literature deal with the existence of paths and cycles in a graph. A subdivision of a multigraph H is any graph obtained by replacing the edges of H with paths of arbitrary length. It is not difficult to see that if H is a path or a cycle, then so too is any subdivision of H. With this observation in mind, it is not surprising that many results that ensure the existence of H-subdivisions in a graph serve to extend existing results about paths and cycles and also to uncover deeper connections between graph properties that may have seemed somewhat unrelated. The long-term goal of the work presented in this talk is to develop a body of work on H-subdivisions that unifies and extends different aspects of the path and cycle literature.

To this end, we discuss several classes of problems related to H-subdivisions. First, we will introduce the notion of an H-linked graph, which extends the classes k-linked, k-ordered and k-connected graphs. We will then discuss conditions that assure the existence of H-subdivisions of many different sizes in a graph, and use our results to obtain some classical results on graph pancyclicity and panconnectivity. We conclude with a discussion of some ongoing work and future directions.

The technology to harvest electricity from wind energy is now advanced enough to make entire cities powered by it a reality. High-quality short-term forecasts of wind speed are vital to making this a more reliable energy source. Gneiting et al. (2006) have introduced a model for the average wind speed two hours ahead based on both spatial and temporal information. The forecasts produced by this model are accurate, and subject to accuracy, the predictive distribution is sharp, i.e., highly concentrated around its center. However, this model is split into nonunique regimes based on the wind direction at an off-site location. This paper both generalizes and improves upon this model by treating wind direction as a circular variable and including it in the model. It is robust in many experiments, such as predicting at new locations. We compare this with the more common approach of modeling wind speeds and directions in the Cartesian space and use a skew-t distribution for the errors. The quality of the predictions from all of these models can be more realistically assessed with a loss measure that depends upon the power curve relating wind speed to power output. This proposed loss measure yields more insight into the true value of each model’s predictions.

NOTE: The Discrete Math Seminar will not meet today. Please attend the talk by the Statistics Candidate at 10:00 AM in the usual room: CU 656. Next week we will have the last of the graph theory candidates on Thursday, February 26. More details will be sent out later. This talk will serve as the Discrete Math Seminar for the week.

The 2008 regular season of the NFL can be represented by a graph. The vertices of this graph are the 32 teams in the NFL. Two vertices are joined by an edge if the corresponding teams play a game during the season (or by two edges if the teams play each other twice). The problem of scheduling the season's games is related to the chromatic index of the graph. We motivate an analogous concept that we call the clique chromatic index by generalizing the above scenario to allow for more than two opponents in a game. We investigate the clique chromatic index for a special class of graphs known as line graphs.

Note: Dr. McClain is a candidate for the graph theory position. Please also note that this talk will be the Discrete Mathematics Seminar for the week, so we will not meet on Monday this week.

When Segre proved his celebrated characterization of conics ("every set of q + 1 points in PG(2; q), q odd, no three of which are collinear, is a conic"), he did more than prove a beautiful and interesting theorem; he in fact provided the starting point of a new direction in combinatorial geometry. In this branch of combinatorics the idea is to provide purely combinatorial characterizations of objects classically de fined in an algebraic way. A result of Ferri and Tallini provides a characterization of Q(4; q) by intersection numbers with respect to planes and solids. This is a clear motivation to look at the following questions:

Is it possible to characterize finite classical polar spaces by their inter- section numbers with respect to planes and solids [2, 3], respectively by their intersections with respect to hyperplanes and subspaces of codimension 2 [1]?

(Note that these questions of course do not make any sense for the polar space W_(2n+1)(q), as this polar space comprises all points of its ambient projective space.)

In this talk we will focus on the first question.

References:

[1] S. De Winter and J. Schillewaert. A characterization of fi nite polar spaces by intersection numbers. Combinatorica, submitted.

[2] J. Schillewaert. A characterization of quadrics by intersection numbers. Des. Codes Cryptogr. 48 (2008), 165 - 175.

[3] J. Schillewaert and J. A. Thas. Characterizations of Hermitian varieties by intersection numbers. Des. Codes Cryptogr. 50 (2009), 41 - 60.

On Monday, April 6, there is no Discrete Math Seminar because we will be meeting with outside reviewers for NCA.

On Friday, April 10 Angela Harris will give a public talk in defense of her Ph.D. thesis. Please consider this to be the Discrete Math Seminar for this week.

On Monday, April 13 there will be no Discrete Math Seminar. Instead, consider attending the spring meeting of the Rocky Mountain Section of the MAA at the School of Mines (both Friday and Saturday).

On Monday, April 20, the Discrete Math Seminar will have the last meeting of the semester. Hank Turowski will be the speaker.

Stan

For adjacency matrix A of a graph G and diagonal matrix D in which the (i,i) entry is the sum of the entries in column i of A, we define the Graph Laplacian of A to be L = D – A. In this talk, we will introduce a technique for ranking the vertices of arbitrary (often very sparse) weighted directed graphs using Graph Laplacians. We will use results of NCAA Division I Basketball games to create A and show that the resulting rankings are reasonable by comparing them to the outcomes of past NCAA Basketball Tournaments.

Abstract: In 1782, Euler considered the problem of placing thirty-six officers--one each of six ranks from each of six regiments--on a six by six grid so that every rank and every regiment is represented in each row and column. It was not until 1900 that Tarry showed that no such configuration could exist. This problem illustrates the concept of orthogonal Latin squares, a concept with important considerations in many areas of mathematics, including the design of statistical experiments, feasible solutions to assignment problems, and combinatorics.

In more recent years, the number puzzle Sudoku has gained popularity, appearing in morning papers everywhere. This puzzle consists of filling in the blanks of a nine-by-nine grid with the numbers one through nine in such a way that every number appears exactly once in each row, column, and three-by-three subsquare. As the solution to a Sudoku puzzle is a Latin square, there is a natural interest in specializing results on Latin squares to Sudoku solutions, and a problem in the American Mathematical Monthly in 2006 asked if there exist orthogonal Sudoku solutions.

In this talk, we review some of the motivation for the study of orthogonal Latin squares and some of the results on orthogonal Latin squares. After introducing these results, we specialize some of the principal constructions of Mutually Orthogonal Latin Squares (MOLS) to construct MOLS with a generalized Sudoku condition (MOSLS). We use a construction from finite fields to construct sets of MOSLS of prime power order and a direct product construction to join these sets for other orders.

This talk does not assume any prior knowledge of the subject matter.

In 1844, J.J. Sylvester published a paper titled "Elementary Researches in the Analysis of Combinatorial Aggregation" which appeared in the Philosophical Magazine (vol. 24). In this paper he introduces the concepts of duads, synthemes and totals which today we would more easily recognize as the edges, 1-factors and 1-factorizations of a complete graph. We shall discuss these graph theoretical concepts and show how they lead to such geometric ideas as Generalized Quadrangles (-Happy Birthday Stan!) and my own sharply focused sets of points in projective planes.

A projective plane is an incidence structure, that is a set of "points" and "lines" with an incidence relation, such that any two points lie on exactly one line, any two lines meet in a unique point, and there exists a set of four points with no three on a common line (this last requirement rules out certain "degenerate" examples). A projective plane can be shown to have precisely as many points as there are lines, and if this number is finite, we have an n where there are n^2 + n + 1 points and lines, and precisely n+1 points on each line. There are known to exist projective planes for n being equal to any prime power, and there is a significant body of theory concerning these types of structures.

We will be focusing on a similiar structure called a biplane. A biplane is an incidence structure such that any two points lie on exactly two lines, and any two lines meet in exactly two points. As with projective planes, a biplane can be shown to have the same number of points and lines. While we have many examples of projective planes, there are only 16 known examples of biplanes, the most recent having been discovered almost 25 years ago. These structures have interesting applications tying together all sorts of ideas from combinatorics, graph theory, geometry, algebra, and coding theory.

In this talk we will look at the history of this rich topic and discuss some of the known existence results. We will also see a few constructions, some involving graph theory, some combinatorial, and some algebraic. This talk will be aimed at being accessible to a wide range of graduate students.

We trace the development of the study of forbidden subgraph results concerning cycle and path properties in graphs. From the first significant development in the early 1980s, through the characterization of forbidden pairs for spanning cycles (hamiltonian graphs), to the characterization of all pairs for 3-connected pancyclic graphs (cycles of all lengths from 3 to the order of the graph) and to the most significant outstanding problem, the Matthews-Sumner Conjecture that all 4-connected claw-free graphs are hamiltonian.

Graph saturation is an area of extremal graph theory made popular by the research of Turan and Erd\"os, Hajnal, and Moon. I am looking in particular at generalizing some of the many existing results on simple graphs to oriented graphs, edge colorings of simple graphs with forbidden monochromatic subgraphs, and avoidance games on oriented graphs.

In many ways graphs can be viewed as discrete analogues of algebraic curves. The recent proof of a Riemann-Roch formula for graphs by Baker and Norine provides an excellent example of such an analogy. In this talk, I will present a discrete framework for linear systems of divisors on graphs compatible with Baker-Norine, and extend their result to edge-weighted graphs, for which there is no obvious continuous analogue.

In this talk I will give a brief history of group theory along with some motivation as to why a person may study in this field. This development will be used to explain what a group extension is, as well as why someone might want to compute them.

Once we have motivated this area, I will talk about how I solve the problem of computing in group extensions. The solution depends upon doing computations using a subgraph of the Cayley Graph. In this development we will be using the concept of a Stalling Folding to prove that two graphs contain the same information. Once we prove that the information contained in both objects is the same, we will show how this can be used to express words as a product of conjugates of relators, and I will explain why this then solves the problem of computing in group extensions.

This talk with the assumes almost no background in group theory beyond what is covered in an introductory abstract algebra course.

*****Please Note the Earlier Start Time***** Given a set S of linear orders of a ground set X, the majority digraph of S is the directed graph on X where there is an edge from u to v when a majority of the orders in S rank u above v. For odd k, a k-majority tournament is a tournament that arises as the majority digraph of a set of k orders. When the orders in S are interpreted as a ranking of preferences among a set of alternatives X, acyclic sets in the majority tournament can be viewed as a consensus ranking of a subset of X. We study the maximum size of an acyclic set of vertices in k-majority tournaments.

Every n-vertex 3-majority tournament contains an acyclic set of size n^{1/2}; we present a family of 3-majority tournaments which have no acyclic sets of size larger than 2n^{1/2}. We show that every n-vertex 5-majority tournament contains an acyclic set of size n^{1/4}. For general k, every k-majority tournament contains an acyclic set of n^{f(k)}, where f(k) = 3^{-(k-1)/2}. On the other hand, there are k-majority tournaments whose largest acyclic sets have size n^{g(k)}, where g(k) = O(log log k / log k). This is joint work with Dan Schreiber and Douglas B. West.

Combinatorial phylogenetics is an area of mathematical biology that uses genetic data available from presently extant organisms to determine their evolutionary relatedness. Determining these historical relationships is important to various areas of research such as evolutionary biology, conservation genetics and epidemiology. I will provide an overview of some widely used evolutionary models focusing on group-based nucleotide substitution models and their use with the Hadamard transform formula. I will also discuss why the Hadamard transform is a useful formula in phylogenetics and mention a few of the approaches used to derive the formula

A (hyper)graph G is F-saturated if G is F-free but the addition of any new edge creates a copy of F. Let sat(n,F) be the smallest size of an F-saturated graph of order n. I will survey this area and present a recent result with Tom Bohman and Maria Fonoberova, where we asymptotically determine the sat-function for an arbitrary complete partite graph F.

In the past half-century, ovals and hyperovals in projective planes have been an area of active research in the field of finite geometry. Connections to other, more applied, areas of mathematics have provided a significant motivation for the study of ovals and hyperovals. In this talk, we give a ground-up introduction to both the theory and history of ovals and hyperovals. In particular, we discuss the classification problem for ovals and hyperovals, including the most recent progress, motivating the problem with an application to error-correcting codes.

The classical centrality functions on trees are the eccentricity, the total distance, and the branch weight, yielding the central sets of vertices called, respectively, the center, the median, and the branch weight centroid. There are many more centrality concepts for trees that yield central sets. Some of the forty or so central sets discussed in our recently completed survey include the telephone center, the latency center, the distance balanced center, the k-ball branch weight center, the Steiner k-center, and the cutting center. In this talk we will sample some of the interesting ones, including some that yield one or two parameter families of central sets. A new, broad generalization involving hereditary classes of trees will be mentioned.

This seminar will consist of two presentations by students in the research group. Titles and abstracts appear below.

--------

Interval Bigraphs with Containment Restrictions

Shilpa Das Gupta

An interval graph is proper if and only if it has a representation in which no interval contains another. Beyerl and Jamison introduced the study of p-improper interval graphs where no interval contains more than p other intervals in 2008. This paper extends the idea by introducing p-improper interval bigraphs, where no interval contains more than p other intervals of the same partite set. Several authors have studied proper interval bigraphs, including one characterization that has three forbidden subgraphs. We find bounds on the p-impropriety of a bigraph and structures of a special case of p-improper interval bigraphs.

--------

P-interval K-trees

Breeann Tonnsen

Interval p-graphs were introduced by Brown, Flink, and Lundgren in 2002 as a generalization of interval bigraphs. Little work has been done towards characterizing them. For interval bigraphs the only known forbidden subgraph characterization is for trees. As it appears to be quite difficult to find a forbidden subgraph characterization, we limit our work to an extension of trees called k-trees. We characterize p-interval k-trees as spiny interior k-lobsters and use this result to give a forbidden subgraph characterization. We apply a similar technique to 2-tree probe interval graphs, studied by Przulj and Corneil in 2005, and characterize them in terms of a subset of spiny interior 2-lobsters.

A graph G is chordal if it contains no induced cycle on four or more vertices and is co-chordal if the complement of G is chordal. Additionally, G is weakly chordal if neither G nor it’s complement contains an induced cycle on five or more vertices, and G is dually chordal if the intersection graph of the maximal cliques of G is chordal. A distance-k matching in a graph G is set M of edges of G such that the minimum distance between distinct edges in M is at least k. Hence, a distance-1 matching is equivalent to an ordinary matching in a graph.

For k at least 2, however, computing the size of the largest distance-k matching in G is NP-hard, and for k = 3, it remains NP-hard even if the graph G is known to be chordal. In this talk, we show that computing the size of the largest distance k-matching can be found in polynomial time when k is even and G is weakly chordal, or when k is odd and G is dually chordal. In addition, we will prove a min-max result for weakly chordal graphs based on the size of the largest distance-2 matching and give a polynomial algorithm to find a minimal set of co-chordal subgraphs which cover the edges of G.

A graph is said to be chordal if it does not have an induced cycle greater than three. A vertex is said to be $k$-simplicial if its neighborhood is a $k$-clique. The smallest $k$-tree is a clique with $k$ vertices. A graph $G$ with more than $k$ vertices is said to be $k$-tree if it has a $k$-simplicial vertex $s_{1}$ such that $G-s_{1}$ is a $k$-tree. Note that a $k$-tree is a chordal graph.

In the paper ``Tough enough chordal graphs are Hamiltonian'' the authors G. Chen, M. S. Jacobson, A. E. K\'ezdy, and J. Lehel showed that $18$-tough chordal graphs are Hamiltonian. It is believed that the actual bound is closer to $2$-tough. I will discuss the status of this problem, and present some advances on finding a tight bound for $k$-trees.

A particularly interesting area of algebraic combinatorics is the relationship between the partitions of the positive integer n and the representations of the symmetric group S_n. For representations over fields of characteristic p (where p is a prime) this relationship is still not well understood. In this talk we will examine three different classes of partitions of n (with respect to the prime p) and the algebraic objects that correspond to each of them. In some cases, the relationships between the class of partitions and the corresponding algebraic objects are known, but in virtually no cases are the relationships between the various classes of partitions known. We’ll look at some related open questions and recent progress on these problems.

Note: Scheduled speaker Hemanshu Kaul will be visiting in June instead, and will give a talk at that time.

A graph $G = (V,E)$ is a sum graph if $V(G) = S \subset \mathbb{N}$ and $E(G) = \{(uv): u + v \in S\}$. It has been proved that for any graph $G$ with $m$ edges, $G \cup m K_1$ is a sum graph. The smallest non-negative integer $\sigma$ such that $G \cup \sigma K_1$ is a sum graph is called the sum number of $G$, denoted $\sigma(G)$. We consider a related problem for quasi-groups. Specifically we show that for any graph $G$ there exists a quasi-group $(Q, \circ)$ with $L(G) \subset Q$ being the labels of the vertices of $G$ such that $(uv) \in E(G)$ if and only if $u \circ v \in L(G)$. We then determine the minimum order of such a quasigroup for several classes of graphs.

A t-(v,k,\lambda) design D is a v-set V with a system of k-subsets (called blocks) such that every t-subset in V is a subset of exactly \lambda blocks. Let p be an element of V. A new design, D_p can be constructed using the point set V-{p} and having all the blocks of D which contain p, without p, as blocks. D_p, the derived design at p, is a (t-1)-(v-1, k-1, \lambda) design. When this process can be reversed, that is, starting with a design with the parameters of a derived design, adding a new point to each of the blocks and finding enough new blocks of the appropriate size to create a t-(v,k,\lambda) design, the new design is called a 1-point extension. The difficulty in such a construction is finding the subsets with the right properties to be the "new" blocks. We shall look at several such constructions with an aim at investigating the open questions concerning Steiner Quintuple Systems (which will be defined in the lecture).

A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given a list A[1:n] of n items, we consider the problem of constructing a data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. We present an O(n)-space static data structure that supports range mode queries in O(sqrt(n/log n)) time in the worst case. This is the first linear-space data structure to guarantee o(sqrt(n)) query time. This is joint work with Timothy Chan, Jason Morrison, and Bryan Wilkinson.

****Note Nonstandard Day and Time**** This talk will discuss the fundamental problems in communication complexity and how linear algebraic and combinatorial techniques and results have lead to some recent breakthroughs.

Given a family of graphs ${\cal F}$, a graph $G$ is ${\cal F}$-saturated if no member of ${\cal F}$ is a subgraph of $G$ but the addition of any new edge to $G$ creates a copy of some member of ${\cal F}$. Let $sat(n, {\cal F})$ denote the minimum number of edges in an ${\cal F}$-saturated graph of order $n$. We say that a graph $H$ arrows a $t$-tuple $(H_1, \ldots ,H_t)$ if any $t$-coloring of the edges of $H$ contains a monochromatic $H_i$-subgraph in color $i$ for some $i\in[t]$. We consider saturated graphs with respect to the family of graphs that arrow $(K_3,K_3)$ and precisely determine the value of the $sat$-function for this family. In doing the latter, we confirm the smallest non-trivial case of a conjecture of Hanson and Toft.

This is joint work with Guantao Chen, Mike Ferrara, Ron Gould, and Colton Magnant.

The original art gallery problem (V.Klee, 1973) asked for the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon (Art Gallery). Chvatal (1975) proved that n/3 guards are always sufficient. Since then many variations of this problem have been studied. We will give a short introduction to many such problems and open questions therein. In particular, we will focus on some progress in Orthogonal Art gallery with holes (a polygon with visibility obstructions whose all edges are either horizontal or vertical). We will illustrate how graph coloring is a major tool for finding such guard assignments.

This seminar has been cancelled.

A uniform polyhedron has regular polygon faces and is vertex transitive. Schwarz triangles are spherical triangles which, by repeated reflections, lead to a set of congruent triangles covering the sphere a finite number of times. This talk will present a kaleidoscopic technique known as Wythoff's Construction which can be applied to Schwarz triangles to derive the set of uniform polyhedra. This approach was used by H.S. M. Coxeter (1954) to produce a complete enumeration of these extraordinary solids.

The Fibonacci sequence F(0) =1, F(1) = 2, F(2) = 3, etc., where F(n) = F(n-1) + F(n-2) (when n is at least 2) has the following two properties:

(1) F(n) is the number of binary strings of length n not containing 11 as a substring.

(2) Each positive integer may be represented in a unique way as the sum of nonconsecutive Fibonacci numbers. (Zeckendorf 1939)

So the Fibonacci sequence (in the form given above) can be used to uniquely represent each positive integer N (this is Numeration), and F(n) counts all strings of a certain kind (this is Enumeration). This talk will study Numeration and Enumeration in a fairly general setting.

A more detailed abstract, along with a self-contained manuscript expanding upon the material in this talk can be found on the UCD Discrete Math Seminar website:

http://math.ucdenver.edu/~mferrara/seminar/F2010/seminar.html

If Earth colonizes its Moon, and cartographers elect to color the corresponding map, they are faced with two planar maps (the map of Earth and the map of its Moon) with an extra coloring constraint: a country and its colony are to be assigned the same color; such a map is called an "Earth-Moon Map."

More generally, the thickness of a graph G, denoted Theta(G), is the smallest integer t such that G can be represented as the edge-disjoint union of t planar graphs. We say that G has thickness t or that G is a thickness-t graph and write Theta(G)=t. Thus if G is planar, then Theta(G)=1. And the graph corresponding to an Earth-Moon map has thickness at most two. In 1959 Gerhard Ringel asked: what is the largest chromatic number of any thickness-two graph? An exact answer continues to be elusive, and the folklore amongst graph colorers is that finding that answer is at least as hard as the proof of the Four Color Theorem, if not harder.

But there are other related problems that are reasonable and interesting to investigate. For example, the r-inflation of a graph G, denoted by G[r], is the graph obtained by replacing each vertex of G with a K_r and then taking the join of neighboring (K_r )s. If chi(G)=k, then chi(G[r]) <= rk and the bound is sharp. What can be said about the thickness of G[r] when, for example, G is planar? This problem and others will be discussed, with open problems given along the way.

This is joint work with Michael O. Albertson and Debra L. Boutin.

An immersion of a graph H in a larger graph G consists of an identification of the vertices of H with branch vertices of G, along with a collection of edge-disjoint paths between these vertices representing the edges of H. This is similar to a subdivision of H which requires the stronger condition that the collection of paths between branch vertices be vertex-disjoint. The study of immersions has recieved much attention recently, due in part to a result of Robertson and Seymour from their graph minors project. We will survey recent results on immersions and relate them to historical results on minors and subdivisions.

Kundu gave a characterization of when a degree sequence of a graph has a realization containing a k-factor. A very intriguing conjectured generalization of Kundu's theorem says that whenever a graph has a realization with a k-factor, it in fact has a realization with k edge-disjoint 1-factors.

Using progress we made on this conjecture as a starting point, we'll talk about a series of related topics, including packing degree sequences, finding k-factors in dense graphs, finding edge-disjoint 1-factors in dense graphs, and applications to domatic coloring, where the color classes are dominating sets.

We trace the development of a strong connectivity condition called Hlinkage. Given graphs G and H, a graph G is said to be H-linked if for any choice of |V (H)| = n distinct vertices of G, we can find a subgraph of G which is isomorphic to a subdivision of H, and in which the selected n vertices play the roles of the vertices of H.

This generalizes the well-known idea of a graph G being k-linked, that is, for any 2k distinct vertices v_1, v_2, . . . , v_k,w_1,w_2, . . . ,w_k there are disjoint paths P_i in G such that P_i joins v_i to w_i. If the graph H is k disjoint copies of K2, then G is k-linked if, and only if, G is H-linked.

We follow the development of linkage theory from simple connectivity (1-linked) to questions concerning general H-linkage. A number of open problems and new questions will be mentioned.

This dissertation proposal concentrates on two topics in Graph Theory, characterizing classes of graphs that have various interval representations and list-coloring classes of graphs to break symmetries.

Interval p-graphs were introduced by Brown, Flink, and Lundgren in 2002 as a generalization of interval bigraphs. Little work has been done towards characterizing them. For interval bigraphs the only known forbidden subgraph characterization is for trees. As it appears to be quite dffcult to find a forbidden subgraph characterization, we limit our work to an extension of trees called k-trees. We characterize p-interval k-trees as spiny interior k-lobsters and use this result to give a forbidden subgraph characterization. We apply a similar technique to 2-tree probe interval graphs and 2-tree unit interval p-graphs, characterizing them in terms of a subset of spiny interior 2-lobsters.

A labeling of the vertices of a graph G is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex labels. The distinguishing number of G, denoted D(G), is the minimum number of labels in a distinguishing labeling of G. The distinguishing number, First introduced by Albertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature. Here, we extend this notion to list-distinguishing colorings. Given a family L of lists assigning available colors to the vertices of G, we say that G is L-distinguishable if there is a distinguishing coloring of of G such that f(v) 2 L(v) for all v. The list-distinguishing number of G, D`(G), is the minimum integer k such that G is L-distinguishable for any assignment L of lists with |L(v)| = k for all v. We will discuss several results including the list-distinguishing number of graphs that realize a dihedral group and the Cartesian product of cycles.

Arrange some vertices in the plane, and some polygon "obstacles", and construct a graph by drawing a straight line edge between vertices whenever it doesn't intersect an obstacle. Which graphs can be constructed in this way? Given a graph, how many obstacles do you need? What if the obstacles are convex polygons? In this talk we'll answer these questions using some surprising connections to a few different topics in graph theory. We'll also pose a number of questions which are still open. This work was done with undergraduate students in the Willamette Valley REU program.

This dissertation proposal concentrates on 4 variations of Interval graphs: Interval digraphs, probe interval graphs, interval k-graphs and interval bigraphs. First we looked at classes of interval digraphs. Interval Digraphs were introduced by Das, Sen, Roy and West in 1989. Considerable research has been done on interval digraphs but no forbidden subgraph characterization has been found. We borrowed ideas from the Interval Tournament paper by Brown, Busch and Lundgren and used the relationship between Interval bigraph and interval digraph to find some new classes of interval digraphs.

Another variation of interval graphs are probe interval graphs. They were introduced in the mid 1990s and like interval bigraphs no forbidden subgraph characterization of probe interval graphs has been found so far. However cycle free probe interval graphs have been characterized by Sheng [1999] and Brown, Lundgren and Sheng characterized cycle free unit probe interval graphs. Corneil and Pruzulj found that 2 tree probe interval graphs have 62 forbidden subgraphs [2005]. Now Brown, Flesch and Lundgren have extended the list and found a characterization of 2-tree probe interval graphs. Here we look at 2 tree unit probe interval graphs and our goal is to find a complete list of forbidden subgraphs.

Interval bigraphs were introduced by Harrary, Kabell and McMorris in 1982. Fred Roberts in 1969 characterized proper interval graphs. In 2008 Beyerl and Jamison introduced the concept of impropriety of interval graphs. We extend the idea of impropriety and look at two variations: Impropriety for interval bigraphs and generalizing it further to impropriety of interval k-graphs.

Many results rely upon moving vertices around within structures to adjust sizes. We will discuss a lemma which does exactly that. Given two paths with many edges between them, this lemma produces a new adjusted pair of paths in which one path has gotten shorter and the other longer. We also discuss many applications of this lemma to results about partitions of graphs.

Given a graph with weighted vertices (initially all 1), an acquisition move transfers weight from a vertex $u$ to neighbor $v$, provided that $v$ has at least as much weight as $u$. The process terminates when the vertices with positive weight form an independent set. The goal is to minimize the size of this final set.

The {\it total}, {\it unit}, and {\it fractional} acquisition numbers are the minimum sizes of the final set when the acquisition moves transfer, all, an integer portion, or any positive portion of the weight from $u$ to $v$, respectively. We present bounds on these parameters and conditions for when they equal 1.

Abstract

***Correction: Date changed to Monday, 11AM. Original Date was incorrect.***

Let H be a multigraph. A subdivision of H, or an H-subdivision, is any simple graph G obtained by replacing the edges of H with disjoint paths of arbitrary length. A graph G is H-linked if every injective function f:V(H) -> V(G) can be extended to an H-subdivision. The notion of an H-linked graphs generalizes those of k-connected, k-linked and k-ordered graphs, each of which has been widely studied in the literature.

In this talk, we give several new degree conditions that assure a graph is H-linked for arbitrary H, refining a 2008 result of Kostochka and Yu. We also give conditions that assure a directed grph is H-linked for arbitrary H, and in the process reveal a previously unobserved contrast between the directed and undirected versions of this problem.

Suppose that every vertex v of a graph G has a list L(v) of "colors." Then G is said to be L-list-colorable if G can be properly (vertex) colored so that each vertex receives a color from its list L.

I will present three open conjectures about list-coloring planar graphs due to Bruce Richter, Michael Albertson, and myself. Each has been verified for outerplanar graphs; in fact, the conjectures were inspired either by the results for outerplanar graphs or by the corresponding (classical) coloring result for planar graphs. Some of the results are joint work with Maria Axenovich and Michelle A. Lastrina of Iowa State University, some are soon to be published results of D. Cranston, A. Pruchnewski, Z. Tuza, and M. Voigt.

Spreads are an important object of study in finite geometry; while they can be characterised in terms of vector spaces, they are best understood when looked at in context of PG(3,q), a three dimensional projective space over a finite field of order q. A spread of PG(3,q) is then a collection of lines that partition the points of the space.

While there are many combinatorial objects related to spreads, we will be looking at collections of lines L having the property that every spread S of PG(3,q) will share precisely x lines with L. Such a set is called a Cameron-Liebler line class of parameter x. In this talk we will discuss some properties of these special line classes and talk about some new results. Using a computer search, new Cameron Liebler line classes with parameter (q^2 -1)/2 have been discovered for several values of q. We will talk about these new examples, and look at some connections to points in affine planes having exactly two intersection numbers with respect to lines. We will also look forward to attempts to prove these examples form part of an infinite family of such line classes.

Brooks' Theorem from 1941 upper-bounds the chromatic number of a graph by the maximum of its clique number and max degree. In 2009, Kierstead and Kostochka proved a similar bound with the max degree replaced by half the Ore degree and conjectured the optimal bound of this form. We discuss the proof of this conjecture and some generalizations. It turns out that for each 0 < \epsilon \leq 1, there is an upper bound of the Brooks' form with max degree replaced by the maximum over all edges of a certain \epsilon-weighted average of the degrees of the ends. Additionally, we prove that if such a bound exists for \epsilon = 0, then P=NP.

Some of this is joint work with Kostochka and Stiebitz.

A polytope is the convex hull of a finite collection of points in Euclidean space, and an automorphism of a polytope is an isometry of the ambient space that leaves the polytope fixed setwise. A flag in an $n$-dimensional polytope $P_n$ is a chain $$ P_0 \subset P_1 \subset \cdots \subset P_n $$ in which $P_i$ is an $i$-dimensional face of $P_n$. If the group of automorphisms of the polytope acts transitively on the flags, the polytope is said to be regular. In 2 dimensions, the regular polytopes are simply the regular polygons, and in 3 dimensions, the regular polytopes are the familiar Platonic solids. I will describe the well-known classification of regular polytopes in $n$-dimensions using the theory of Coxeter groups. I will also discuss more general examples of non-regular polytopes in which the automorphism group of the polytope acts transitively on the faces of dimensions $0$ and $1$ (vertices and edges). I will describe some of the topological and combinatorial properties of these polytopes, including the graphs that arise from their vertices and edges.

This work is supported by NSF grant DMS-0905768.

A graph is said to be chordal if it does not have an induced cycle greater than three. A vertex is said to be $k$-simplicial if its neighborhood is a $k$-clique. The smallest $k$-tree is a clique with $k$ vertices. A graph $G$ with more than $k$ vertices is said to be $k$-tree if it has a $k$-simplicial vertex $s_{1}$ such that $G-s_{1}$ is a $k$-tree. Note that a $k$-tree is a chordal graph.

In the paper ``Tough enough chordal graphs are Hamiltonian'' the authors G. Chen, M. S. Jacobson, A. E. K\'ezdy, and J. Lehel showed that $18$-tough chordal graphs are Hamiltonian. It is believed that the actual bound is closer to $2$-tough. I will discuss the status of this problem, and present some advances on finding a tight bound for $k$-trees.

Stacks and Queues are typically the first sophisticated computational structures encontered when one learns how to program a computer. A superficial study of the structures might lead one to expect them to be roughly equal in “computational power”:

- They have quite similar structures when implemented in a traditional programming language.

- They seem to embody mutually dual ordering disciplines: LIFO (Last-In, First-Out) for the Stack and FIFO (First-In, First-Out) for the Queue.

A deeper analysis of the two structures uncovers a much more textured conclusion about their comparative “computational powers.” This talk will describe some fascinating and unexpected highlights of a gedanken tour of Stack-and-Queue Land, with stops at which we look at Stacks and Queues within the contexts of:

1) “universal storage structures” (a la Turing Machine tape)

2) permutation generators

3) mechanisms for linearizing graphs

4) mechanisms for scheduling parallel computations.

Starting with the high school concept of a circle, we will trace the generalizations of this idea which occur when the background geometry is generalized. The end result of this series of abstractions is the combinatorial structure called a Buekenhout Oval which is defined without reference to any particular geometry.

A graph $G$ is said to be hamiltonian if it contains a spanning cycle. Given a family ${\mathcal F}$ of graphs, we say that a graph $G$ is ${\mathcal F}$-free if $G$ does not contain a copy of any of the graphs in ${\mathcal F}$ as an induced subgraph.

Various types of conditions guaranteeing that $G$ is hamiltonian have been studied. Included in these types of conditions is finding families of graphs ${\mathcal F}$ such that all $k$-connected ${\mathcal F}$-free graphs are hamiltonian.

One way to extend the concept of hamiltonicity is through pancyclicity. A graph $G$ is said to be pancyclic if it contains a cycle of each length from 3 up to $|G|$. We will discuss families of graphs ${\mathcal F}$ such that $k$-connected ${\mathcal F}$-free graphs are pancyclic. In particular, we will discuss some new results concerned with the case where ${\mathcal F}$ is a long path.

A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given a list A[1:n] of n items, we consider the problem of constructing a data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. We present an O(n)-space static data structure that supports range mode queries in O(sqrt(n/log n)) time in the worst case. This is the first linear-space data structure to guarantee o(sqrt(n)) query time. This is joint work with Timothy Chan, Jason Morrison, and Bryan Wilkinson.

We are interested in finding new algorithms for standard linear algebra operations that enables high degree of parallelism and low communication requirement. The need for such algorithms is motivated by the apparition of multicore platforms, but they also prove useful in hybrid computation (CPU+GPU), parallel distributed computation (cluster of nodes with MPI interconnect), or even grid computing. In this context, the so-called tile algorithms are good candidates and their study is a current research topic.

In this talk, we will mainly focus on (1) the QR factorization of a matrix, (2) multicore context, (3) tile algorithms.

This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, greedy, and those found within the PLASMA library. Although neither Modi and Clarke nor greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q^2 f(q), where f is any function such that lim_{+\infty} f= 0. This novel and important complexity result applies to all matrices where p and q are proportional, p = \lambda q, with \lambda \geq 1, thereby encompassing many important situations in practice (linear least squares). We provide an extensive set of experiments that show the superiority of the new algorithms for tall matrices.

This is joint work with Henc Bouwmeester, Mathias Jacquelin and Yves Robert.

We present a general approach to the problem of optimizing a variety of graph invariants over the class of trees with a given degree sequence. This extends the approach of Biyikoglu and Leydold concerning the tree with given degree sequence having the largest eigenvalue of its adjacency matrix. We characterize exactly the trees with: the largest number of independent sets, the minimum number of matchings, the smallest Weiner index, the largest number of homomorphisms to a fixed strongly biregular graph, and the maximum number of subtrees. We also show that these values are strictly monotone with respect to majorization.

This apparently This apparently eclectic talk will begin with a result about the Boolean rank of upset tournament matrices which was initialized by Lundgren and Siewert in 2003 and settled by Brown and Roy in 2011. The method used for establishing this result provides a segue into the problem of finding the intersection number of a graph or digraph and a relationship between that number and the Boolean rank, and, therefore, to a relationship between the aforementioned and the dot-product dimension of a graph or digraph.

Now for the definitions of terms just mentioned. The \emph{Boolean rank} of an $m \times n$ $(0,1)$-matrix $M$ is the minimum $k$ such that there is an $m \times k$ matrix $A$ and a $k \times n$ matrix $B$ such that $AB=M$, where the arithmetic is done over the Boolean anti-negative semiring (where $1+1 =1$, and hance $A$ and $B$ must be $(0,1)$-matrices). The Boolean rank of $M$ has connections to the minimum number of bicliques required to cover the edges or arcs of (di)graph $G$, where $M$ is the adjacency matrix of $G$. The \emph{intersection number of $G$} is the minimum cardinality of the union of sets $S_1, S_2, \dots, S_n$ which can be put into bijective correspondence with vertices of graph $G$ such that vertices of $G$ are adjacent if and only if their corresponding sets intersect. The intersection number of a digraph is defined similarly, but to each vertex $v$ of digraph $D$ there corresponds an ordered pair of sets $(S_v,T_v)$ with $u \to v$ in $D$ if and only if $S_u \cap T_v \neq \O$.

Finally, let $f$ map the vertices of $G$ to vectors in $k$-dimensional real space such that vertices are adjacent if and only if the dot-product of their corresponding vectors is greater than or equal to $1$; the \emph{dot-product dimension of $G$} is the minimum $k$ for which such an $f$ exists.

Many times we'd like a graph to have a particular special or popular property, and often these properties are quite hard to detect. Consequently a large body of research in the area is aimed at developing good sufficient conditions that, when satisfied, guarantee that a given graph has a given property.

In this talk we look at theorems that give sufficient conditions on a graph's degree sequence; when the conditions on the degree sequence are satisfied, the graph is guaranteed to have certain properties. For a few properties the theorems so far discovered are, in a sense we'll describe, the best humanly possible. On the other hand, many graph properties of long-standing interest have no best possible degree sequence theorems. We illustrate both cases by looking at the property of being t-tough. In this case, for certain values of toughness we've managed to prove the best possible theorem, while for other values we've discovered and proved that these best possible theorems aren't actually possible.

Minkowski's Lattice Point Theorem is the start of a branch of number theory known as the geometry of numbers. It guarantees that a centrally symmetric convex set whose volume is sufficiently large must have a nonzero lattice point. We will present the basic definitions and results needed to understand this, and will then apply Minkowski's Theorem to certain diophantine equations.

For example, we will show that an odd prime p can be written in the form

p = x^2 + 2y^2

provided p is of the form p = 8k + 1 or of the form p = 8k + 3.

Those little bars and boxes that permit optical scanning are ubiquitous in our modern world. Zip codes, ISBN's, UPC codes at the grocery store and even those funny looking square TAG boxes that are popping up everywhere, are purposely designed to catch both machine and human errors. We will look at a variety of examples to uncover the mathematical basis for the error detection capabilities of scan codes.

***Note Corrected Date*** Tropical Geometry is concerned with transforming questions in algebraic geometry into combinatorial questions in polyhedral geometry. Tropical mathematics has its origins in optimization theory, following the work of the Brazilian mathematician Imre Simon in the development of the min-plus algebra. In addition to algebraic geometry, tropical geometry has applications in number theory, phylogenetics, and graph theory. In this talk, we will develop tropical arithmetic and the min-plus algebra, discuss tropical curves and their connections to algebraic curves, and give an overview of some applications of tropical geometry.

This presentation will examine two classes of problems in graph theory. 1. An interval graph G = (V,E) is a graph in which each vertex is associated with an interval of the real line with two vertices adjacent if and only if their corresponding intervals intersect. Interval graphs can be generalized by partitioning the intervals into interval and placing restrictions on when members of various interval classes induces edges in G. For example, in interval k-graphs an edge exists only when intersecting intervals are from different interval classes.

We generalize this concept by defining a homomorphism phi : V (G) --> V (H) to some graph H, and allowing an edge xy in E(G) only when the associated intervals intersect, and phi(x)phi(y) is in E(G). We call the resulting class of graphs interval H-graphs.

2. The irregularity strength, s(G), of a graph G is defined as the minimum k such that there exists an edge weighting function f : E(G) to [k] in which no two vertices have the same weighted degree. This definition can be extended to directed graphs by defining the degree of a vertex as either the ordered pair

d(v) = (d^+(v), d^−(v)) or as d(v) = d^+(v)−d^−(v).

We will examine some results on the irregularity strength of graphs, orientations of simple graphs and directed graphs and discuss several open problems.

We show that any k-uniform hypergraph with n edges contains two edge disjoint subgraphs of size \tilde{\Omega}(n^{2/(k+1)}) for k=4,5 and 6. This result is best possible up to a logarithmic factor due to a upper bound construction of Erd\H{o}s, Pach, and Pyber who show there exist k-uniform hypergraphs with n edges and with no two edge disjoint isomorphic subgraphs with size larger than \tilde{O}(n^{2/(k+1)}). Furthermore, this result extends results Erd\H{o}s, Pach and Pyber who also established the lower bound for k=2 (eg. for graphs), and of Gould and R\"odl who established the result for k=3. We will discuss the techniques used in the proof, which are both combinatorial and probabilistic. We will also discuss the difficulties that arise with this problem as k increases. These necessitate the use of some less commonly used probabilistic tools, notably a concentration inequality of Chatterjee for certain functions of random permutations.

A graph is a prime distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is prime. Surprisingly, some well-known theorems and longstanding conjectures in number theory are closely connected to questions about prime distance graphs. In this talk we'll investigate some of these connections and fail to prove any of the longstanding conjectures.

A linear extension of a partially ordered set is simply a total ordering of the poset that is consistent with the original ordering. The linear extension diameter is a measure of how different two linear extensions could be, that is, the number of pairs of elements that are reversed. I will calculate the linear extension diameter of grids, generalizing a method of focusing on sub-cubes that was developed in a 2011 paper by Felsner and Massow. This also gives us a nice characterization of the linear extensions that are the farthest from each other.

The nontrivial finite generalized polygons include 3-gons (projective planes), 4-gons (generalized quadrangles), 6-gons (generalized hexagons), and the 8-gons (generalized octagons). Only one family of generalized octagons is known, the so-called Ree-Tits octagons.

After introducing the main concepts we will outline a computer-assisted proof that there is a unique generalized octagon of order (2,4) that contains a suboctagon of order (2,1). Our analysis of this example allows us to describe three classes of hyperplanes of the Ree-Tits octagon of order (2,4).

In 1998 M.O. Albertson asked the following question: given a planar graph G with lists of 5 colors assigned to each vertex, does there exist a d>0 such that whenever a subset of vertices P is such that the distance between every pair of vertices in P is at least d, then every precoloring of P extends to a 5-list-coloring of G? Z. Tuza and M. Voigt have shown that if such a d exists, then d>4. In this talk based on work with M. Axenovich and J.P. Hutchinson, we present classes of planar graphs for which Albertson's question has an affirmative answer.

***** The following presentation will serve as Timothy Morris' PhD research proposal.*****

A graph G is said to be hamiltonian if it contains a spanning cycle. Given a family F of graphs, we say that a graph G is F-free if G does not contain a copy of any of the graphs in F as an induced subgraph. Various types of conditions guaranteeing that G is hamiltonian have been studied. Included in these types of conditions is finding families of graphs F such that all k-connected F-free graphs are hamiltonian.

One way to extend the concept of hamiltonicity is through pancyclicity. A graph G is said to be pancyclic if it contains a cycle of each length from 3 up to G. We will discuss families of graphs F such that k-connected F-free graphs are pancyclic. In particular, we will discuss some new results concerned with the case where F contain a long path, as well as some future directions.

Note that a hamiltonian cycle is a 2-factor containing only one component. Forbidden subgraph conditions have been determined for both the existence of both 1-factors and 2-factors. If a graph $G$ contains disjoint 1-factors, then G contains a 2-factor such that every component is even. We propose the investigation of forbidden subgraph conditions that assure a graph has a pair of disjoint 1-factors. As a first step, we discuss a recent proof of the stability of the existence of a pair of disjoint 1-factors under the Ryjacek closure.

Advisory Committee:

Michael Ferrara (Advisor)

Michael Jacobson

Paul Wenger

Ellen Gethner (UCD Computer Science and Engineering)

Ronald J. Gould (Emory University)

An interval graph G=(V,E) is a graph in which each vertex is associated with an interval of the real line with two vertices adjacent if and only if their corresponding intervals intersect. Interval graphs can be generalized by partitioning the intervals into interval classes and placing restrictions on when members of various interval classes induces edges in G. For example, in interval k-graphs an edge exists only when intersecting intervals are from different interval classes.

We generalize this concept by defining a homomorphism f: V(G) -> V(H) to some graph H, and allowing an edge xy in G only when the associated intervals intersect, and edge f(x)f(y) exists in H. We call the resulting class of graphs interval H-graphs. In this talk, we will characterize acyclic interval P_4-graphs and discuss interval P_n-graphs in general. Time permitting; we will present recent work toward finding polynomial time recognition algorithms for interval P_n-graphs.