

Algebra, Combinatorics, and Number Theory Seminar
Wednesday, April 16^{th}, 2014 at
10:00am NS 212F
Ms. Heather Hunt
University
of Louisville
Abstract:
Let G be any arbitrary group and C the field of complex
numbers. I will present all functions f, g, h, k : G x G => C that satisfy
the linear functional equation
f(pr,qs) + g(ps,qr) = h(p,q) + k(r,s)
for all p, q, r, s in G and the structure of the solution of the nonlinear
functional equation
f(pr,qs) + f(ps,qr) = g(p,q) h(r,s)
for all p, q, r, s in G. I will give several examples related to a specific
case of the linear equation.

Past Seminars...
Wednesday, April 9^{th}, 2014 at
10:00am NS 212F
TOTAL CHROMATIC SUM FOR GRAPHS
Professor Ewa Kubicka
University
of Louisville
Abstract:
The total chromatic sum of a graph is the smallest sum of colors (positive
integers) over all proper colorings of edges and vertices. For vertex coloring
there are families of graphs requiring more colors than the chromatic number
to achieve the vertex chromatic sum. The similar phenomenon occurs for edge
chromatic sum.
During the seminar talk I will focus on constructions of graphs requiring
more colors than the total chromatic number to achieve the total chromatic
sum.
This is a joint work with Grzegorz Kubicki and Max Leidner.

Wednesday, April 2^{nd}, 2014 at
10:00am NS 212F
Axiomatic characterization of center functions
Professor Jake Wildstrom
University
of Louisville
Abstract:
A location consensus function is a function mapping a finite sequence of
graph vertices (called the profile) to a nonempty subset of the graph's
vertices (called the consensus); the underlying concept is that the consensus
function result is the set of points which are in some way "equitable" locations
for a service being voted on by many individuals in the profile. As with
other voting and consensus problems, a question often asked about location
consensus is how certain functions may be characterized by sensible axioms.
Location functions such as the median and other L_{p} metrics have
been extensively studied; the center function (which selects as the consensus
points those which are at a minimum distance from the most distant elements
of the profile) is quite different in that multiplicity of a single location
has no effect on the result. Some variations of the center, however, do
take multiplicity into account.
In this talk I will discuss ongoing progress towards axiomatically characterizing
the center function on a variety of graphs  particularly median graphs.
This is a collaboration with Buck McMorris, Martyn Mulder, and Bob Powers,
and some previous characterizations by Mulder, Pelsmajer, and Reid as well
as some relevant work of Kezdy and Powers will also be discussed.

Wednesday, March 26^{th}, 2014 at
10:00am NS 212F
The chordal graph homomorphism problem  Part
II
Professor Steve Seif
University
of Louisville
Abstract:
Chordal graphs are interesting; semilattices are semiinteresting, and in
this talk, the two will be brought together: Chordal graphs will be shown
to admit semilattice polymorphisms. Having a semilattice polymorphism is
a nice property for a graph, since, as is known (and will be proven in the
talk), such graphs have a polynomialtime retraction problem.
The talk will be based on a recent paper by P. Hell and M. Siggers in
which the authors present a new characterization of chordal graph, one
given in terms of certain semilattice polymorphisms. The authors present
several easily stated problems, aimed at understanding the class of graphs
that admit semilattice polymorphisms, and these problems will be discussed.
Background on chordal graphs, graph polymorphisms, the retraction problem
etc. will be given in this chalkandtalk, selfcontained discussion. All
are welcome.

Wednesday, March 19^{th}, 2014 at
10:00am NS 212F
The chordal graph homomorphism problem  Part
I
Professor Steve Seif
University
of Louisville
Abstract:
Chordal graphs are interesting; semilattices are semiinteresting, and in
this talk, the two will be brought together: Chordal graphs will be shown
to admit semilattice polymorphisms. Having a semilattice polymorphism is
a nice property for a graph, since, as is known (and will be proven in the
talk), such graphs have a polynomialtime retraction problem.
The talk will be based on a recent paper by P. Hell and M. Siggers in
which the authors present a new characterization of chordal graph, one
given in terms of certain semilattice polymorphisms. The authors present
several easily stated problems, aimed at understanding the class of graphs
that admit semilattice polymorphisms, and these problems will be discussed.
Background on chordal graphs, graph polymorphisms, the retraction problem
etc. will be given in this chalkandtalk, selfcontained discussion. All
are welcome.

Wednesday, March 5^{th}, 2014 at
10:00am NS 212F
The ABC Matrix Scheme of Ding
Professor Daniel SmithTone
University
of Louisville
Abstract:
Last summer Jintai Ding of UC and a few other scientists presented a new
multivariate encryption scheme. The idea of a multivariate encryption scheme
is offensive to me for reasons I’ll explain in this presentation. The basic
task is to illustrate that the cryptosystem doesn’t perform as indicated by
the creators. The talk will consist of a review of multivariate constructions
and fundamental complexity theoretic problems related to inverting a system
of polynomial equations, a description of Ding’s scheme, and an analysis of
some of the algebraic properties of the scheme. Breaking the scheme is still
(possibly) open, and so fresh ideas are welcome.

Wednesday, February 19^{th}, 2014 at
10:00am NS 212F
Arrovian Consensus of Partial Orders
Professor Robert Powers
University
of Louisville
Abstract:
K. Arrow (1963) proved that it is impossible for a social welfare
function to be nondictatorial, Pareto, and independent of irrelevant alternatives.
Arrow’s approach to social welfare and, in particular, his impossibility
result has made a lasting impact on both the economic and mathematical communities.
For example, there are versions of Arrow’s Impossibility Theorem for partial
orders, interval orders, semiorders, equivalence relations, tree quasiorders,
hierarchies, and weak hierarchies. In this presentation, I will talk about
the version of Arrow’s Theorem for partial orders and some related results.

Wednesday, February 12^{th}, 2014 at
10:00am NS 212F
Optimal stopping for avoiding capture in a random
walk on a cycle
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
We want to maximize the number of moves for a random walk on an even
cycle before visiting the vertex opposite to the starting position. Our
payoff is the number of moves but it is reduced to 0 if we are not able to
avoid the opposite vertex. Optimal stopping time and the expected value of
the payoff are determined. For the corresponding process with N stages, the
asymptotic behavior of the expected payoff is established as N increases
without bound.

Wednesday, January 29^{th}, 2014 at
10:00am NS 212F
Thomas Lane
University
of Louisville
Abstract:
We explore the structure of the permutation representation of group
actions on CWATsets. We also generalize an analogue of Sylow's first theorem
to (X, M)CWATsets.

Wednesday, January 15^{th}, 2014 at
10:00am NS 212F
Proof of the removable pair conjecture for fractional
dimension of posets
Csaba Biro
University
of Louisville
Abstract:
Recall that a realizer of a poset P consists of some of its linear
extensions, such that their intersection is P. The minimum cardinality
of a realizer is called the dimension of P. The dimension is "continuous",
i.e. removing a point from P can not decrease its dimension by more than
1. Trotter conjectured in 1971 that every poset has a pair of points whose
removal does not decrease the dimension by more than 1. This has become
known as the removable pair conjecture. In 1992 Brightwell and Scheinerman
introduced a fractional version of dimension, and conjectured that the
Removable Pair Conjecture holds for fractional dimension. We settle this
latter conjecture in the affirmative. The proof is simple and elegant,
so I will try to explain it in full. (Joint work with Peter Hamburger and
Attila Por.)

Wednesday, December 4^{th}, 2013 at
1:00pm NS 212D
Dealing with Hamiltonian cycles
Jeno Lehel
Visiting
Scholar, University of Louisville
Abstract:
As a "Hamiltonian cycle nonexpert" I joined recently a project dealing
with the following problem: Find a Hamiltonian cycle such that two given
vertices of the graph are located on that cycle at a given distance.
I will talk about a few tools what I learned from my cycle specialist
coauthors Ralph Faudree and Kiyoshi Yoshimoto.

Wednesday, November 20^{th}, 2013 at
1:00pm NS 212D
My Favorite Graph Theory Conjecture
Martyn Mulder
Econometrisch
Instituut, Erasmus Universiteit, Rotterdam, Netherlands
Abstract:
At the 2014 Joint Mathematics Meeting next January in Baltimore there
is a Special Session "My Favorite Graph Theory Conjectures", in which
I will participate. The title of this talk is derived from this Special
Session. In 1990 I formulated a MetaConjecture that reads "Any
(sensible) property shared by the trees and the hypercubes is shared
by all median graphs", with the Strong version: "Any (sensible) property
shared by the trees and the hypercubes characterizes the median graphs".
Of course, in order to make sense, we have to be more specific about
what a "sensible" property is. In this talk these MetaConjectures are
explained and it is shown what fruit these have borne over the years.
Also some possibilities for open problems are discussed.

Wednesday, November 6^{th}, 2013 at
1:00pm NS 212D
Revisit Pascal's Theorem from algebra
Jinjia Li
University
of Louisville
Abstract:
Pascal's Theorem, originally discovered by Pascal in the 1600s, is
a theorem in plane geometry which predicts that three pairs of opposite
sides of a hexagon inscribed in a circle meet in three collinear points.
We will discuss how this follows from a deeper theorem of Max Noether,
concerning intersection cycles of (projective) curves. I will make this
talk accessible to people with no background in algebraic geometry. Students
with a brief understanding of polynomial rings (such as k[X,Y] or k[X,Y,Z])
and ideals in such rings should be able to follow most part of the talk.

Wednesday, October 30^{th}, 2013
at
1:00pm NS 212D
Graph minors and apex graphs
Andre Kezdy
University
of Louisville
Abstract:
A graph is an apex graph if it contains a vertex whose deletion produces
a planar graph. The family of apex graphs is a basic minorclosed family,
yet the finite list of minorminimal apex obstructions remains unknown.
We have recently determined all minorminimal apex obstructions that
have connectivity two (there are well over 100). In this talk I will
present these graphs, sketch the main ideas in our proof to show the list
is complete, and comment on our progress finding all minorminimal apex
obstructions. I will also briefly introduce fundamental concepts related
to graph minors and motivate the study of apex graphs in this larger context.
Several open problems will be interspersed.
This is joint work with Adam Jobson and Csaba Biro

Wednesday, October 23^{rd}, 2013
at
1:00pm NS 212D
Partition adjacency matrices
Eva Czabarka
University
of South Carolina
Abstract:
HavelHakimi and respectively Ryser showed that the space of graphs
and bipartite graphs with a given degree sequence is connected under
simple swaps of edges. This operation is useful in an MCMC algorithm
that samples the space of graphs with a given degree sequence. Degree
sequence alone does not capture the assortativity of the graph, the tendency
of nodes to be connected to vertices of similar or different degrees.
To overcome this difficulty, the joint degree matrix of a graph was introduced.
Partition adjacency matrices (PAMs) are generalizations of joint degree
matrices: given a partition $\{P_1, \ldots,P_M\}$ of the vertex set the
$M\times M$ partition adjacency matrix $(a_{ij})$ is defined by $a_{ij}=$
the number of edges connecting a vertex in $P_i$ to a vertex in $P_j$.
We will show conditions for a matrix to be the partition adjacency matrix
of a graph; prove that under certain condition essentially the same swaps
connect the space of all graphs with a given PAM, and give examples that
show that these conditions are the best possible in some sense.
Possible extensions and open questions will be discussed. This
is joint work with Aaron Dutle, and in part with P.L. Erd\H{o}s and Istv\'an
Mikl \'os.

Wednesday, October 16^{th}, 2013
at
1:00pm NS 212D
Connected Matchings in Chordal Bipartite Graphs
Adam Jobson
University
of Louisville
Abstract:
Motivated by applications to Hadwiger's Conjecture, Plummer, Stiebitz,
and Toft introduced connected matchings: a collection of edges that
pairwise are nonintersecting but joined by another edge of the graph.
It is known that determining if a graph has a connected matching of size
at least k is NPcomplete for general graphs and even for general bipartite
graphs, but the problem is polynomialtime solvable for chordal graphs
(graphs with no induced cycle of length greater than three). We show that
the problem is polynomialtime solvable for chordal bipartite graphs (bipartite
graphs with no induced cycle of length greater than four) and discuss how
this relates to the Hadwiger number of chordal bipartite graphs.
Joint
work with André Kézdy and Susan White

Wednesday, October 9^{th}, 2013 at
1:00pm NS 212D
Extending the PCTree Algorithm to the Torus
Charlie Suer
University
of Louisville
Abstract:
Planar graphs have been well studied and there are many lineartime
algorithms for determining if a given graph is planar. In particular,
we take a detailed look at the PCTree Algorithm of Shih and Hsu.
The torus and toroidal graphs are less understood, so we present an
extension of the PCTree algorithm that will determine if a graph in
a certain class is toroidal. This will hopefully open the door to
a practical, fast toroidal algorithm for all graphs.

Wednesday, September 25^{th}, 2013
at
1:00pm NS 212D
Iadic completions of modules over commutative
rings
Hamid Kulosman
University
of Louisville
Abstract:
Iadic completions of modules over Noetherian commutative
rings are wellbehaved, but if the ring is not Noetherian the situation
becomes complicated. We illustrate this on an example and discuss some
statements that can help in this case.

Wednesday, September 18^{th}, 2013
at
1:00pm NS 212D
A finite algebras approach to a class of computational
complexity problems
Steven Seif
University
of Louisville
Abstract:
Constraint satisfaction problems (CSPs) are a class of computational
complexity problems (all in NP) that encompass many classes of well
studied problems including kCOL, kSAT, HCOL (coloring by a graph
H), and numerous other natural problems. About 15 years ago, it was
conjectured that CSPs admit dichotomy: Every CSP is either in P or is
NPcomplete. In this talk, algebraic tools that can be used to classify
CSPs are described, and an Algebraic CSP Dichotomy Conjecture (first presented
about 12 years ago) is described.
There are no prerequisites, and basics of computational
complexity will be gone over. Anyone familiar with basic algebra structures
(groups and lattices would do) will have no problem with the algebra
discussed.
Unfortunately, to do all this, means that I will give the
talk using slides. The talk should last about 75 minutes with a three
minute break at the 50 minute mark.

Wednesday, September 4^{th}, 2013
at
1:00pm NS 212D
Pathwidth and dimensions
Csaba Biro
University
of Louisville
Abstract:
The oldtime belief among poset theorists used to be that
the structure of the cover graph of a poset (which is just the Hasse
diagram, but the orientation is removed) says little about the invariants
of the poset. For example there are posets with planar cover graphs that
are of arbitrarily large dimension. But recently Joret et. al proved that
the dimension of a poset is bounded by a function of its height and the
treewidth of its cover graph. They posed the question (among others)
if pathwidth at most two of the cover graph implies bounded dimension.
We answer this question in the affirmative.
This is joint work with Mitchel T. Keller and Stephen J.
Young.

Wednesday, April 17^{th}, 2013 at
2:30pm NS 212D
Giant Components in Random Graphs
Mary Radcliffe
University
of Washington
Abstract:
Many models for generating random graphs begin with a fixed
collection of vertices, and a rule for defining the probability that
two vertices are adjacent. Here, we consider how the analysis of a random
graph changes in certain cases where we allow both the vertex set and
edge set to be chosen randomly. In particular, we will consider the eigenvalues
of such graphs, and the emergence of the giant component in one such model,
the Multiplicative Attribute Graph.
(some of this is joint work with Stephen J. Young.)

Wednesday, April 10^{th}, 2013 at
2:30pm NS 212D
Acyclic and IndifferenceTransitive Collective
Choice Functions
Mrs. Katey Bjurstrom
University
of Louisville
Abstract:
Arrow's classic theorem shows that any collective choice
function f satisfying independence of irrelevant alternatives (IIA)
and Pareto (P), where the range is a subset of weak orders, is based
on a dictator. Recent work in social choice theory has shown that if
the range is changed to the set of acyclic, indifferencetransitive relations
on the set of alternatives, X, then the outcome is instead a weak dictator.
In this talk, we will investigate the particular case where the number
of voters is limited to 2, and X=4.

Wednesday, April 3^{rd}, 2013 at
2:30pm NS 212D
May's Theorem on Median Semilattices
Mr. Lucas Hoots
University
of Louisville
Abstract:
In 1952, Kenneth May published a set of necessary and suffcient
conditions that characterized simple majority rule in the case of 2
alternatives. We extend May's Theorem beyond the classical setting by
using the theory of ordered sets and, in particular, the theory of median
semilattices.

Wednesday, March 27^{th}, 2013 at
2:30pm NS 212D
Efficiency of limitedknowledge relocation of
highmobility and lowmobility resources
Professor Jake Wildstrom
University
of Louisville
Abstract:
Relocation of serviceproviders in response
to changing realtime needs is suboptimal due to limited foreknowledge
of client requests. Simple cost schedules for relocation and remoteservice
provision have been investigated both for the possibility of complete
optimizability and the degree of inefficiency introduced by imperfect
future knowledge. Traditionally, relocation and remoteservice costs
have been regarded as identical, but the introduction of a mobility
parameter reflects the realistic element that many resources can provide
service to remote clients with ease, but incur massive expenses in relocating.
The optimizability response to this parameter exhibits two significant
thresholds, dividing the range of parameter values under consideration
into "highmobility", "mediummobility", and "lowmobility". Highmobility
resources have trivial optimization, and mediummobility resources exhibit
difficulttocharacterize behavior, but most realworld applications
involve lowmobility resources, which have, in many cases, a surprisingly
straightforward characterization.

Wednesday, March 20^{th}, 2013 at
2:30pm NS 212D
Online Linear Discrepancy of Partially Ordered
Sets
Professor Mitchel T. Keller
University
of NebraskaLincoln
Abstract:
The traditional framework
for algorithm design for discrete structures involves the algorithm
knowing the entire structure when it begins it run. An online algorithm,
in contrast, receives information about the structure one point at
a time and must make an irrevocable decision about how to treat that
point. For instance, an online coloring algorithm is given a new vertex
and told which of the existing vertices are its neighbors and must decide
how to color it based upon that information. Linear discrepancy can
be thought of as a way to measure the "unfairness" of a linear extension
of a partially ordered set in terms of placing incomparable elements
far apart in the linear extension. In this talk, I'll discuss linear
discrepancy and then what we know about online algorithms for determining
it as well as a bit about work in progress to extend these ideas. This
is joint work with Noah Streib and William T. Trotter. The work in progress
is with Jamie Radcliffe.

Wednesday, March 6^{th}, 2013 at
2:30pm NS 212D
Problems in finite lattice theory
Professor Steve Seif
University
of Louisville
Abstract:
The Finite Lattice Representation Problem (FLRP), a sixtyyearold
open problem, will be discussed. Connections will be made between FLRP
and representations of lattices as congruence lattices of finite transitive
and intransitive permutation groups. A series of easily stated problems
in finite lattice theory will be presented, and the speaker will review
his recent results on representations by intransitive permutation groups.
All are welcome.

Wednesday, Jan. 23^{rd}, 2013 at
2:30pm NS 212D
Indifferentiability Security for Hash Modes
Professor Daniel Smith
University
of Louisville
Abstract:
A hash function is a map which accepts as input strings
of arbitrary finite length and produces a fixed length output in
such a way that it is computationally difficult to achieve the same
output with any other input. A hash mode is a construction which builds
such a function from functions with finite domain (called primitives).
The indifferentiability framework is a model for proving the security
of hash modes. We will introduce the indifferentiability framework, discuss
some of the history of proof technique in this framework, and present
a new technique which seems more powerful and generalizable to more powerful
security proofs.

Tuesday, Nov. 27^{th}, 2012 at
10:00am NS 212D
Consensus Functions on Distributive Semilattices
Professor Robert Powers
University
of Louisville
Abstract:
A distributive semilattice is a meet semilattice X such
that every principal ideal of X is a distributive lattice. A consensus
function on X takes as input any ktuple of elements from X and outputs
a nonempty subset of X. In this talk, I will introduce three conditions
a given consensus function may or may not satisfy and show that the
only consensus function that satisfies all three conditions is a special
type of median function.

Tuesday, Nov. 13^{th}, 2012 at
10:00am NS 212D
Spectral Graph Theory and the AlonBoppana Theorem
Professor Stephen Young
University
of Louisville
Abstract:
We will give an overview of the ideas and motivation behind
spectral graph theory leading up to the AlonBoppanna bound on the
spectrum and its recent generalizations.

Tuesday, Oct. 23^{rd}, 2012 at
10:00am NS 212D
Introduction to Percolation Theory  Part III
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Percolation theory, founded half a century ago, models the
flow of fluid in a porous medium with randomly blocked channels. Usually,
the underlying graph is a lattice, or at least some highly vertextransitive
graph, and to obtain a random subgraph (called an open graph) we
select edges (for bond percolation) or vertices (for site percolation)
independently with the same probability p. There is a variety of percolation
problems, but in this talk (and possibly a short series of talks) we
will examine the probability of having an infinite component in the open
graph. Above some value of p, called a critical probability, the probability
of having an infinite component is nonzero.
After introducing some necessary notation and terminology
(mostly following the book: Bollobas and Riordan "Percolation"
, 2006), we will discuss a bond percolation on the infinite binary tree
and on the infinite square lattice Z^2. In the letter case, the famous
HarrisKesten Theorem from 1980 established the critical probability
to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Oct. 16^{th}, 2012 at
10:00am NS 212D
Introduction to Percolation Theory  Part II
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Percolation theory, founded half a century ago, models the
flow of fluid in a porous medium with randomly blocked channels. Usually,
the underlying graph is a lattice, or at least some highly vertextransitive
graph, and to obtain a random subgraph (called an open graph) we
select edges (for bond percolation) or vertices (for site percolation)
independently with the same probability p. There is a variety of percolation
problems, but in this talk (and possibly a short series of talks) we
will examine the probability of having an infinite component in the open
graph. Above some value of p, called a critical probability, the probability
of having an infinite component is nonzero.
After introducing some necessary notation and terminology
(mostly following the book: Bollobas and Riordan "Percolation"
, 2006), we will discuss a bond percolation on the infinite binary tree
and on the infinite square lattice Z^2. In the letter case, the famous
HarrisKesten Theorem from 1980 established the critical probability
to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Oct. 2^{nd}, 2012 at
10:00am NS 212D
Introduction to Percolation Theory Part I
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Percolation theory, founded half a century ago, models the
flow of fluid in a porous medium with randomly blocked channels. Usually,
the underlying graph is a lattice, or at least some highly vertextransitive
graph, and to obtain a random subgraph (called an open graph) we
select edges (for bond percolation) or vertices (for site percolation)
independently with the same probability p. There is a variety of percolation
problems, but in this talk (and possibly a short series of talks) we
will examine the probability of having an infinite component in the open
graph. Above some value of p, called a critical probability, the probability
of having an infinite component is nonzero.
After introducing some necessary notation and terminology
(mostly following the book: Bollobas and Riordan "Percolation"
, 2006), we will discuss a bond percolation on the infinite binary tree
and on the infinite square lattice Z^2. In the letter case, the famous
HarrisKesten Theorem from 1980 established the critical probability
to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Sept. 25^{th}, 2012 at
10:00am NS 212D
Professor F.R. McMorris
Illinois
Institute of Technology and University of Louisville
Abstract:
Let G =(V,E) be a finite connected graph and pi a ktuple in V.
Location and consensus theory often involves finding the set of vertices
x, for which D(x,pi) is minimum, where D(x,pi) is some measure of the
"remoteness" of x to pi. A function that returns, for any pi, the set
of vertices minimizing D is called a location function and the problem
of characterizing such functions has been a challenge for more than
20 years. A survey of some old and new results are presented, while
focusing on the case where G is a tree and where three popular versions
of D are used.

Tuesday, Sept. 12^{th}, 2012 at
10:00am NS 212D
How to Build a Multivariate Cryptosystem
Professor Daniel Smith
University
of Louisville
Abstract:
We go through the construction of several multivariate cryptosystems
and explore some results on security in this area. We'll also introduce
some new problems in this area which may challenge the predominant
perspective on the field. This talk should be accessible and interesting
to graduate students.

Tuesday, Sept. 4^{th}, 2012 at
10:00am NS 212D
Explorations into the maximum length of Hajnal's
TriangleFree Game
Professor Jake Wildstrom
University
of Louisville
Abstract:
Hajnal proposed a game where two players successively add edges to
an initiallyempty trianglefree graph on n vertices until no more
edges can be added without violating the trianglefree condition. One
player seeks to end the game quickly, while the other player seeks to
extend the game as long as possible. The only proven upper bound on length
of a game with rational play is the value n^2/4, which occurs even with
suboptimal play by the player seeking a quick ending. Joint work with
Paul Horn and Csaba Biró has constructed a strategy which provides
some hope of pushing this boundary down closer to the
occasionally cited conjectural bound of n^2/5.

Tuesday, Aug. 28^{th}, 2012 at
10:00am NS 212D
The uniform attachment process
Professor Csaba Biro
University
of Louisville
Abstract:
Consider a sequence of nonnegative integers $d_0,d_1,d_2,\ldots$
with the property $d_i\leq i$. We assign a random graph on countably
infinitely many vertices $v_0,v_1,\ldots$ to this sequence, defined
by the following process. Start with no edges. Then for $i=0,1,\ldots$,
in the $i$th step, choose a subset $B$ of $\{0,1,\ldots,i1\} uniformly
at random, and add edges between $v_i$ and $v_j$ for all $j\in B$.
We study the resulting probability space.
The talk will start with some introduction on the ErdosRenyi
infinite graph (aka Rado graph), and it should be accessible to
even beginning graduate students.
Joint work with Udayan B. Darji.

Wednesday, April 18^{th}, 2012 at
2:00pm NS 212D
Secretary problem, its generalizations, and efficient
stopping algorithm on directed acyclic graphs
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Secratary Problem is about stopping on the best element in a linearly
ordered set of order n. Elements are revealed one by one in some random
permutation and there is no return to the elements in the past. Optimal
strategy is given and shortly justified. Generalizations of the secretary
problem to partially ordered sets are discussed as well as generalizations
to graphs and digraphs. In the last part of the talk, a new efficient
algorithm for stopping on a sink in a directed acyclic graph is presented.

Wednesday, April 11^{th}, 2012 at
2:00pm NS 212D
A New Class of Linear Codes for Cryptographic
Uses
Professor JonLark Kim
University
of Louisville
Abstract:
We introduce a new class of rate one half binary codes: complementary
information set codes. A binary linear code of length 2n and dimension
n is called a complementary information set code (CIS code for short)
if it has two disjoint information sets. This class of codes contains
selfdual codes as a subclass. Such codes permit to improve the cost
of masking cryptographic algorithms against side channel attacks. In this
paper we investigate this new class of codes: we give optimal or best
known CIS codes of length < 132: We derive general constructions based
on cyclic codes and on double circulant codes. We derive a VarshamovGilbert
bound for long CIS codes, and show that they can all be classi ed in small
lengths up to 12 by the building up construction.
This is a joint work with Claude Carlet, Philippe Gaborit,
and Patrick Sole.

Wednesday, April 4^{th}, 2012 at
2:00pm NS 212D
3connected $\{K_{1,3}, P_9\}$free Graphs are
Hamiltonian Connected
Paul Wrayno
Western
Kentucky University
Abstract:
We show that any graph that is 3connected and does not have either
the claw, $K_{1,3}$, nor the path on 9 vertices, $P_9$, as an induced
subgraph is hamiltonian connected. This result is part of a program
of classifying all pairs of forbidden subgraphs that imply hamiltonian
connectedness or more broadly characterizing pairs of forbidden graphs
that imply some hamiltoniantype property. We are also able to restrict
the possible pairs that can imply hamiltonian connectedness. In this talk
we will also discuss some of the history in this area, and demonstrate some
of the more useful tools for tackling problems in this area.

Wednesday, March 28^{th}, 2012 at
2:00pm NS 212D
Majority Decision and Median Semilattices
Professor Bob Powers
University
of Louisville
Abstract:
In 1952, Kenneth May gave a simple and elegant characterization
of the simple majority voting rule. In 2003, Gerhard Woeginger extended
May's theorem to the case where the set of voters is allowed to vary.
In this talk, I will explain how to generalize Woeginger's result to
the context of (finite) median semilattices.

Wednesday, March 21^{st}, 2012 at
2:00pm NS 212D
Stack Domination of Graphs and Graph Mycielskians
Professor Jake Wildstrom
University
of Louisville
Abstract:
For any given graph G, the domination numbers of the Cartesian product
of G and either the path P_n or cycle C_n are asymptotically linear;
the coefficient of linearity can be regarded as
the "density" of a dominating set within the "stack" of
identical graphs described by its product with a path. Some earlier
work on the general stack domination number will be covered in this
work, as well as progress in an ongoing exploration of how this parameter
varies between a graph and its Mycielskian.

Wednesday, March 7^{th}, 2012 at
2:00pm NS 212D
Online chain partitioning of posets
Professor Csaba Biro
University
of Louisville
Abstract:
The classic theorem of Dilworth states that if the size of a maximum
antichain of a poset is w, then the poset can be partitioned into
w chains. In the online version of this problem, the question is the
existence of a "good" chain partitioning algorithm, which doesn't receive
the poset at once, but instead, the poset is given by an adversary one
point at a time. We survey some old and new results on the topic, and
we explore some new ideas for improved algorithms.

Wednesday, February 15^{th}, 2012
at
2:00pm NS 212D
On an enumerative problem by Kezdy and Snevily
(part 2)
Professor Jake Wildstrom
University
of Louisville
Abstract:
This continues a topic begun last semester. Previously we looked
at an enumerative variation on Snevily's conjecture, to wit: for a given
sequence of k distinct elements of Z_n, how many permutations of the
numbers (1,2,3,...k) are there which, when added termwise to the sequence,
yield k terms which are all distinct? This value is trivially zero if
k>n, and a result of Hall shows that there are sequences for which it
is zero if k=n. However, the number of permutations for even a worstcase
sequence appears to be nonzero for k < n. Snevily and Kezdy calculated
several values, and conjectured that this number is furthermore monotonic
in n and monotonic in k (up to k=n1). This talk will present several
observations and results related to this problem, explicitly proving monotonicity
for certain values of n and k and presenting viable frameworks for continuing
explorations.

Wednesday, December 7^{th}, 2011
at
2:00pm NS 212D
On an enumerative problem by Kezdy and Snevily
(part 1)
Professor Jake Wildstrom
University
of Louisville
Abstract:
Following up on the talk of two weeks ago about Arsovski's proof
of Snevily's conjecture, I will present the current state of research
on an enumerative problem related to a variant of the previous problem.
The question addressed previously considered the possibility of permuting
a sequence of k distinct elements of an abelian group so that its
termwise sums with a specific other sequence of k distinct elements
were all distinct. If we relax the requirement that both sets have distinct
elements, then certain aspects of this problem become more difficult.
We will look at a specific variant of this problem which is less algebraically
general, in which the group in question is Z_n, and the second sequence
is {1,2,3,...,k}.
Snevily and Kezdy conjectured that, if k < n, there
is at least one permutation pi of any sequence {a_1,...,a_k} such
that the sums a_pi(1) + 1, a_pi(2) + 2, ..., a_pi(k) + k in Z_n. They
further proposed an enumerative interpretation of this property, asking
which sequences possess the fewest such permutations, and how many
permutations they have. This talk will present observations relating
to this enumeration, proofs of the known relationships, and productive
ongoing approaches to strengthening those results.

Wednesday, November 30^{th}, 2011
at
2:00pm NS 212D
Large chromatic number and Ramsey graphs
Professor Csaba Biro
University
of Louisville
Abstract:
Let $Q(n,c)$ denote the minimum clique size an $n$vertex graph
can have if its chromatic number is $c$. Using Ramsey graphs we give
an exact, albeit implicit, formula for the case $c$ is at least $(n+3)/2$.
Joint work with Zoltan Furedi and Sogol Jahanbekam.

Wednesday, November 16^{th}, 2011
at
2:00pm NS 212D
Arsovski's proof of Snevily's conjecture
Professor Hamid Kulosman
University
of Louisville
Abstract:
Additive Combinatorics is an area which is highly active in the last
1015 years. One of the reasons is a long list of famous conjectures
raised in this period. To mention some of them: four Snevily's conjectures,
Quistorff's conjecture, KezdySnevily conjecture, DasguptaKarolyiSerraSzegedy
conjecture, Sun's conjecture, and others. Also the influential books
``Additive Combinatorics" (Tao and Vu, 2006) and ``Combinatorial Number
Theory and Additive Group Theory" (Geroldinger and Ruzsa, 2009) appeared
in this period. In this talk we will pay attention to one of Snevily's
conjecture (Snevily's third conjecture, 1999). It has a very simple formulation:
Let A and B be two kelement subsets of a finite abelian
group of odd order. Then there is a numbering a1, a2, ..., ak of the
elements of A and a numbering b1, b2, ..., bk of the elements of
B such that the sums a1+b1, a2+b2, ..., ak+bk are all distinct.
Despite the efforts of many mathematicians, it remained
open for ten years. Finally in 2009 a young Macedonian mathematician
Bodo Arsovski published a proof of it. We will go through Arsovski's
proof (which is quite elementary), but will also present Alon's simple
proof of a stronger statement in one particular case. Even though it
is solved, Snevily's third conjecture raises several other questions.
In the recent paper by Sun (2011), he uses Commutative Algebra (more
precisely, Exterior Algebras, a major object in Commutative Algebra)
to prove some related statements.

Mathematics Seminar
and Colloquium
Wednesday,
November 9^{th}, 2011 at
2:00pm NS 212D
Coloring with Distance Constraints:
The Packing Chromatic Numbers of a Graph
Professor Wayne Goddard
Clemson
University
Abstract:
Let $S=(a_1, a_2, \ldots)$ be an infinite nondecreasing sequence
of positive integers. An $S$packing $k$coloring of a graph $G$ is
a mapping from $V(G)$ to $\{1,2,\ldots,k\}$ such that vertices with color
$i$ have pairwise distance greater than $a_i$ and the $S$packing chromatic
number $\chi_S(G)$ of $G$ is the smallest integer $k$ such that $G$
has an $S$packing $k$coloring. This concept generalizes both proper
colorings and broadcast colorings. In this talk we explore broadcast
colorings and this generalization. This includes bounds, exact values,
and some surprising complexity results.

Wednesday, October 26^{th}, 2011
at
2:00pm NS 212D
Diagonal Fthreshold, HilbertKunz multiplicity and socle
degrees of Frobenius powers
Professor Jinjia Li
University
of Louisville
Abstract:
Let (R,m)
be a local ring in prime characteristics. The diagonal Fthreshold
(i.e, the Fthreshold of m with respect to an mprimary ideal I)
is known to exists as a real number in either the Fpure on the punctured
spectrum case or in the standardgraded complete intersection case.
In this talk, we make connections between the rationality of this invariant
with that of the HilbertKunz multiplicity by investigating the socle
degrees distribution of the Artinian quotient of R (modulo the Frobenius
powers).

Wednesday, October 19^{th}, 2011
at
2:00pm NS 212D
The Core of a Strongly Stable Ideal
Bonnie Smith
University
of Kentucky
Abstract:
In this talk we consider strongly stable ideals of degree two.
Each of these ideals can be thought of as the edge ideal of a graph
with loops. More specifically, Corso and Nagel have studied them
as examples of ``specializations of generalized Ferrers ideals." Like
Ferrers ideals, strongly stable ideals of degree two correspond to a
tableau having a certain shape. We survey some facts about strongly
stable ideals, then come to a specific object associated to a strongly
stable ideala subideal called the core. We introduce the core of
an ideal, whose study is motivated by the study of blowup algebras
and several geometric connections. There are very few classes of ideals
where a closed formula for the core is known. We will see how the special
properties of a strongly stable ideal, having to do with the associated
tableau, allow us to find a surprisingly simple formula for the core of
the ideal.

Wednesday, October 12^{th}, 2011
at
2:00pm NS 212D
Optimum Distance Profiles of Binary SelfDual Codes
Finley Freibert
University
of Louisville
Abstract:
Selfdual codes have widespread relations to various areas such as
combinatorial designs, unimodular lattices, and group theory. A
selfdual code is called {\em doublyeven}
or {\em Type II} if the weights of the codewords are divisible
by 4. Let $C$ be a binary $[n,k]$ code and let $C_0=C$. A sequence
of linear subcodes of $C$, $C_0 \supset C_1 \supset \cdots \supset
C_{k1}$ is called a {\em subcode chain}, where the dimension of $C_i$
is $ki$ for $i=0,
\dots k1$. Let $d_i:=d(C_i)$ be the minimum distance
of $C_i$. Then the sequence $d_0 \le d_1 \le \cdots \le d_{k1}$
is called a {\em distance profile} of $C$. Luo, Vinck, and Chen (2010)
have studied the optimum distance profiles of ReedSolomon
codes, Golay codes, the first order ReedMuller codes, and the second
order ReedMuller codes. In this talk, we examine optimum
distance profiles of extremal Type II codes of lengths
24 and 32, and give some direction towards the optimum distance profiles
of codes of greater lengths. This is a joint work with JonLark
Kim.

Wednesday, October 5^{th}, 2011
at
2:00pm NS 212D
Two open problems of finite algebras
Professor Steve Seif
University
of Louisville
Abstract:
A lattice L is algebraic if every element in it is the join of compacts
elements of L. For example, the lattice of subalgebras of any algebra
is algebraic, as is its congruence lattice. In 1963, G. Gratzer and
T. Schmidt proved that every algebraic lattice is the congruence lattice
of some algebra. They asked if it is true that every finite lattice
is the congruence lattice of a finite algebra, and the question remains
open 48 years later. P.P. Palfy and P. Pudlak proved in 1980 that the question
has a ``yes'' answer if and only if a similar question involving finite
groups has a ``yes'' answer. The PalfyPudlak result brought the finite
group theory community into the chase. The speaker will provide all definitions,
along with examples, outline the PalfyPudlak result, and describe the
current status of the question.
As is the case with some longstanding open problems,
the lattice representation question (described above) has lead to
significant development in the area of finite algebras. In addition
to the lattice representation problem  time permitting the speaker
will discuss these developments, particularly in connection with
constraint satisfaction problems, an area that now lives at the boundary
of the theory of finite algebras, computational complexity, and combinatorics.
This will be a ``chalk and talk'' presentation, structured
but informal, without any significant algebra prerequisites, and
the talk (most of it) should be accessible to those who find groups,
rings, and posets of interest.

Wednesday, September 21^{st}, 2011
at
2:00pm NS 212D
What is the depth of a module (ideal, ring, etc.)?
Professor Jinjia Li
University
of Louisville
Abstract:
Stanley conjectured that in the graded setting, the depth of a module
is less than or equal to its Stanley depth. In our AlgebraCombinatorics
seminar on 09/07/11, Csaba Biro talked about the definition of Stanley
depth and how to compute it. The purpose of this talk is to complement
the talk of Csaba regarding Stanley's conjecture by giving a brief introduction
to the notion of depth of a module in commutative algebra. In particular,
we will introduce how to compute depth, what important roles does depth
play in commutative algebra, and the related notion of CohenMacaulayness
(CohenMacaulay rings and CohenMacaulay modules).

Wednesday, September 14^{th}, 2011
at
2:00pm NS 212D
Graph theoretic study of the homeomorphism group
of the Cantor
space with applications to Conjugacy Relation and Dynamics
Professor Udayan Darji
University
of Louisville
Abstract:
In this paper we introduce and develop graph theoretic techniques
to study the dynamics and the structure of the homeomorphism group
of the Cantor space. We establish an important
approximation theorem and give an invariant which determines
when two homeomorphisms of the Cantor space are conjugate to each
other. Our investigation leads to an unified view point from which many
well known and new results follow with ease. For example, Kechris and
Rosendal
proved that the homeomorphism group of the Cantor space
admits generics and an explicit description of the Special Homeomorphism
was given by Akin,Glasner and Weiss. Our investigation gives a simpler
and more explicit description of the Special Homeomorphism. As a simple
corollary to our techniques we show that a generic homeomorphism of
the Cantor space has no LiYorke pair, which implies the well known result
of Glasner and Weiss that a generic homeomorphism of the Cantor space
has topological entropy zero. In addition to other applications to the
dynamics of homeomorphisms, we also develop similar but simpler techniques
in order to study the dynamics of the generic continuous selfmap of
the Cantor space.

Wednesday, September 7^{th}, 2011
at
2:00pm NS 212D
Interval partitions of the hypercube and its
connections with commutative algebra
Professor Csaba Biro
University
of Louisville
Abstract:
Herzog et al. discovered an algorithm that computes the Stanley depth
of a monomial ideal of a polynomial ring by considering partitions
of certain finite posets into intervals. Motivated by this, they posed
the question whether it is possible to partition the nonempty subsets
of $\{1,\ldots,n\}$ into intervals $[X_i,Y_i]$ with $Y_i\geq n/2$.
In this talk, we introduce the notion of Stanley depth, and answer their
question affirmatively by giving a construction of such a partition.
(Joint work with David Howard, Mitch Keller, Tom Trotter
and Stephen Young.)

Thursday, February 24^{th}, 2011
at
1:00pm NS 212D
Open problems from finite rings, groups, and
more general finite algebraic structures
Professor Steven Seif
University
of Louisville
Abstract:
Two open problems from finite rings will be discussed; one is longstanding
problem
seeking a characterization of the socalled critical finite
commutative rings; the other finite involves the computational
complexity of determining whether a polynomial is identically 0
over a given finite ring R. Results, conjectures, recent work involving
analogous problems from finite group theory will be also be presented.
Basic general (= universal) algebras notions such as congruences, congruence
lattices, again in connection with open problems some longstanding,
but all reasonably accessible. These will include the Finite Lattice
Representation problem (which has connections with finite group theory)
and, if time permits, the (Algebraic) Constraint Satisfaction Conjecture,
which conjectures that constraint satisfaction problems admit a
dichotomy into P and NPcomplete problem as determined by the algebraic
structure of finite universal algebras. All are welcome. Grad students
are especially welcome.

Thursday, February 17^{th}, 2011
at
1:00pm NS 212D
A Combinatorial Approach to Height Sequences
in Finite Posets
Professor Csaba Biro
University
of Louisville
Abstract:
Fix an element $x$ of a finite partially ordered set $P$ on $n$ elements.
Then let $h_i(x)$ be the number of linear extensions of $P$ in which
$x$ is in position $i$, counting from the bottom. The sequence $\{h_i(x):1\le
i\le n\}$ is the \emph{height sequence} of $x$ in $P$. In
1982, Stanley used the AlexandrovFenchel inequalities
for mixed volumes to prove that this sequence is logconcave, i.e.,
$h_i(x)h_{i+2}(x)\le h_{i+1}^2(x)$ for $1\le i\le n2$. However,
Stanley's elegant proof does not seem to shed any light
on the error term when the inequality is not tight; as a result,
researchers have been unable to answer some challenging questions
involving height sequences in posets. In this paper, we provide a
purely combinatorial
proof of two important special cases of Stanley's theorem
by applying Daykin's inequality to an appropriately defined distributive
lattice. This is joint work with W.T.Trotter.

Tuesday, November 30^{th}, 2010
at
1:30pm NS 317
Stack Domination Density
Professor Jake Wildstrom
University
of Louisville
Abstract:
Vizing's conjecture presents one of the most wellknown bounds on
the domination number of a Cartesian product of arbitrary graphs. We
explore specifically the domination number of a graph's product with
a large path or cycle, and consider the asymptotic density of dominating
elements in an arbitrarily large ``stack'' of multiple copies of a graph
$G$. This quantity is specifically calculated for several common graphs
and for the Gr\"otzch graph. We will also explore the dominationdensity
effects of substituting other families of graph for the path and the
cycle as the underlying stack shape.

Tuesday, November 9^{th}, 2010 at
1:30pm NS 317
A functional equation related to elemenary school
arithmetic
Professor Ron Sahoo
University
of Louisville
Abstract:
In this talk I will show how an interesting functional equation arises
from the elementary school arithmetic and then I will present its
solution on an abelian group. This equation has a long and rich history,
with connects to factor systems, group extensions, cohomology theory,
information theory, formal groups, the algebra of polyhedra, and Jordan
derivation. The talk will be accessible to graduate students.

Tuesday, November 2^{nd}, 2010 at
1:30pm NS 317
Fraisse limits and generics in groups  Part
2
Professor Udayan Darji
University
of Louisville
Abstract:
Continuation of last week's talk.

Tuesday, October 26^{th}, 2010 at
1:30pm NS 317
Fraisse limits and generics in groups  Part
1
Professor Udayan Darji
University
of Louisville
Abstract:
In recent years Fraisse limits have found themselves
intimately involved with certain types of structures in groups. In
this talk I will give an introduction to Fraisse limits and its connections
with the concept of generics in groups introduced by Truss in the 90's.
I will also try to formulate some interesting questions in this line
of investigation related to some of my past work. Everything will be
defined and should be accessible to anyone who knows what a group is.
Graduate students are more than welcome to attend.

Tuesday, October 19^{th}, 2010 at
1:30pm NS 317
Upper bounds on the domination number of graphs
with given
minimum degree
Professor Csaba Biro
University
of Louisville
Abstract:
A dominating set of a graph is a subset $X$ of
the vertices such that every vertex is adjacent to some vertex in
$X$ (or is in $X$ itself). The domination number $\gamma(G)$ of a graph
is the minimum cardinality of a dominating set. Alon and Spencer showed
that $\gamma(G)\leq\frac{1+\ln(\delta+1)}{\delta+1}n$, where $n$
is the number of vertices and $\delta$ is the minimum degree. We show
some ideas about how to improve on this bound, including a new bound
for regular graphs that is best known for $\delta\geq 6$. Joint work
with E. Czabarka, P. Dankelmann and L. Szekely.

Tuesday, October 5^{th}, 2010 at
1:30pm NS 317
A tale of two combinatorial identities
Professor Jinjia Li
University
of Louisville
Abstract:
I will discuss a pair of elementary combinatorial
identities
which come surprisingly from some nontrivial observations
in algebra.

Tuesday, September 28^{th}, 2010
at
1:30pm NS 317
How discharging methods can get us closer to
proving the total coloring conjecture for planar graphs
Max Leidner
University
of Louisville
Abstract:
Total coloring was introduced in the late 60s,
and Behzad & Vizing proposed the conjecture that X"(G)<=D(G)+2
(where D=maximum degree). So far this is open, although for planar
graphs it has been proved for D<6 and D>6. A method of induction
based on size, with the analysis of "reducible" configurations and
the use of a discharging technique to prove their existence, was used
to prove the D=7 case by Sanders and Zhao in 1999, and seems like a
promising way to close the gap by proving the D=6 case. During the talk
I will summarize some of my research into this problem, more specifically,
that the conjecture is true for D=6 if you restrict each vertex to being
part of 3 or fewer 3cycles.

Tuesday, September 14^{th}, 2010
at
1:30pm NS 317
The 2distance coloring of the Cartesian product
of cycles
using optimal Lee codes
Professor JonLark Kim
University
of Louisville
Abstract:
Let C_m be the cycle of length m. We denote the
Cartesian product of n copies of C_m by $G(n,m):=C_m \square C_m
\square \cdots \square C_m$. The kdistance chromatic number $\chi_{k}
(G)$ of a graph G is $\chi(G^k)$ where G^k is the kth power of graph
G = (V, E) in which two distinct vertices are adjacent in G^k if and
only if their distance in G is at most k. The kdistance chromatic number
is related to optimal codes over the ring of integers modulo m with minimum
Lee distance k+1. In this paper, we consider $\chi_{2}(G(n,m))$ for n=3
and m => 3. In particular, we compute exact values of \chi_{2}(G(3,m))$
for 3 <= m <= 8 and m = 4k for any positive integer k, and upper
bounds for m >= 9. We also show that the maximal size of a code in Z_6^3
with minimum Lee distance 3 is 26.
joint work with SeogJin Kim

Tuesday, August 31^{st}, 2010 at
1:30pm NS 317
How to check that a set of polynomials over a
commutative ring is a Grobner basis
Professor Hamid Kulosman
University
of Louisville
Abstract:
We will first talk about the notion of a Grobner
basis over a field (about the
history and the importance of that notion). Recently people
started studying Grobner basis
over general commutative rings. We will talk about some
results in that direction and raise
some questions.

Wednesday, April 21^{st}, 2010 at
1:00pm NS 130
About Hilbert's Nullstellensatz
Professor Hamid Kulosman
University
of Louisville
Abstract:
Hilbert's Nullstellensatz is one of the most
famous theorems in Mathematics. It was proved in the late nineteenth
century. We will start our talk by explaining the original statement
and some of its variations. There are some special situations in which
the statement can be more precise. One of the recent developments
of that type is the socalled Combinatorial Nullstellensatz by Alon.
We will talk about the proofs of that statement and applications to
other areas.

Wednesday, March 24^{th}, 2010 at
1:00pm NS 130
Codes in Random Network Coding
Finley Freibert
University
of Louisville
Abstract:
Yeung & Zhang introduced the concept of network
coding theory in 1999. Since then, network coding theory has become
very popular because of its wide applications. Koetter & Kschischang
in 2008 considered a random network coding and introduced the Hamming
bound, the GV bound, and the Singleton bound for codes in the finitefield
Grassmannian. In this talk, we overview recent developments of these
codes. This is a joint work with JonLark Kim.

Wednesday, February 10^{th}, 2010
at
1:00pm NS 333
McGarvey's Theorem for Losers
Professor Robert Powers
University
of Louisville
Abstract:
In 1953,
David McGarvey showed that if the number of voters is unrestricted,
then the set of outputs obtained from majority rule is a very general
class of binary relations. We will present an analog of McGarvey's Theorem
based on a new version of majority rule where the set of outputs is
a very general class of ternary relations. This is joint work with
Lee Gibson.

Wednesday, November 13 and 20^{th},
2009 at
2:00pm NS 333
Dynamical Systems and Cellular Automata  Part 1 (Nov. 13)
and Part 2 (Nov. 20)
Professor Udayan Darji
University
of Louisville
Abstract:
In this talk we discuss a powerful result of
Boyle from which a very useful characterization of cellular automata
follow. This characterization is useful in studying Sutner's problem
which Steve Seif discussed last fall in the seminar.

Wednesday, October 17^{th}, 2009
at
1:00pm NS 333
Open Problems
Professor André Kézdy
University
of Louisville
Abstract:
I will mention several open problems in discrete
mathematics, some of which have been considered at the open problems
workshops during the past two summers. Included will be the sortingpairsinbins
problem, an antipermanent conjecture, and Rado's conjecture. Different
parts of this talk are joint work with Adam Jobson, Hunter Snevily
and Susan White.

Wednesday, April 15^{th}, 2009 at
1:30pm NS 333
Properties of csequences
Professor Hamid Kulosman
University
of Louisville
Abstract:
The notion of a dsequence was introduced in
1980s by Craig Huneke and was a generalization of the notion of a
regular sequence, one of the most important notions in Commutative
Algebra. The notion of a csequence is in turn a generalization of the
notion of a dsequence. Like regular and dsequences, csequences also
generate ideals of linear type. They are in a way the weakest type
of sequences that allow an inductive procedure for generating ideals
of linear type. We will discuss various properties of csequences and
compare them with analogous properties of dsequences. We will raise
several questions.

Wednesday, March 4^{th}, 2009 at
2:00pm NS 333
A brief look at Binary Social Choice
Professor Robert Powers
University
of Louisville
Abstract:
Suppose there is a society consisting of at least
three individuals and each individual votes for one out of two alternatives
or they abstain. In this context, an aggregation function takes an
ordered list of votes as input and outputs a winner or declares a
tie. I will introduce the notion of a quota pair system and show that
an aggregation function satisfies the conditions of anonymity and monotonicity
if and only if it is uniquely determined by a quota pair system.

Wednesday, November 19^{th}, 2008
at
1:00pm NS 333
Introduction to lattices from codes
Professor JonLark Kim
University
of Louisville
Abstract:
There has been a remarkable connection between codes and
lattices, in particular, between selfdual codes and unimodular
lattices in R^n. For examples, the Gosset lattice E_8
in R^8 and the
Leech lattice in R^{24} are easily constructed from the
Z_4lifts of
the binary Hamming code of length 8 and the binary Golay
code of
length 24, respectively. In this talk, we will introduce
basic
definitions about codes and lattices, and describe several
construction methods including Construction A and B.
We stress how
codes over rings are important in constructing interesting
lattices. Finally we conclude with some open problems
generalizing
isodual lattices.

Wednesday, November 12^{th}, 2008
at
1:00pm NS 333
Computation Models and Algebra
Professor Steve Seif
University
of Louisville
Abstract:
Several models of computation, including cellular automata,
finite state automata, and Turing machines will be presented,
mainly
by example.
The computational complexity of several problems will
be discussed,
and in so doing, the definitions of classes such as "P"
and "NP"
(and others) will be given.
The role of algebra, in particular universal algebra,
in the
determination of the complexity of algorithms will be
discussed.

Wednesday, November 5^{th}, 2008
at
1:00pm NS 333
Metric Properties of Maximal Outerplanar
Graphs
Ben Allgeier
University
of Louisville
Abstract:
Maximal Outerplanar graphs (MOPs) can be viewed as
triangulated polygons. The interval I[u,v] between vertices
u and v is
the set of all vertices on some shortest uv path. For
a subset W of
vertices, the interval I[W] is the union of all I[u,v]
with u and v in
W. If I[w] = V(G), then we say W is a geodetic set of
G. We give the
characterization of all geodetic sets of MOPs. Then Steiner
sets will
be defined and we compare the Steiner sets and geodetic
sets of
MOPs. We also define convex sets and discuss the convexity
of
intervals.

Wednesday, October 22^{nd}, 2008
at
1:00pm NS 333
A Version of the Secretary Problem on a Complete
Bipartite Graph
with Random Size of Partite Sets
Professor Ewa Kubicka
University
of Louisville
Abstract:
Consider a complete bipartite graph G of odd order 2n+1 in which
the
size of one partite set is given by a binomial distribution
with
p=1/2. The vertices of G are observed one by one in a
random order and
the subgraph induced by them is revealed. We find the
optimal
stopping time maximizing the probability of stopping on
a vertex from
the smaller partite set. The probability of success is
given and its
asymptotic behavior is established. This is collaborative
work with
Grzegorz Kubicki.

Wednesday, October 15^{th}, 2008
at
1:00pm NS 333
Approximations of automorphisms on the kcolored
random graph  Part II
Professor Udayan Darji
University
of Louisville
Abstract:
In this talk we discuss basic properties of the kcolored
random graph R. In particular, we show that algebraically
speaking,
the kcolored random graph is unique and, moreover, it
contains a copy
of every kcolored finite graph. We discuss some results
of Truss
concerning the cycle structure of automorphisms on R.
We also discuss
some of our results (joint with James Mitchell) concerning
approximations of automorphisms on R.

Wednesday, October 8^{th}, 2008
at
1:00pm NS 333
Approximations of automorphisms on the kcolored
random graph  Part I
Professor Udayan Darji
University
of Louisville
Abstract:
In this talk we discuss basic properties of the kcolored
random graph R. In particular, we show that algebraically
speaking,
the kcolored random graph is unique and, moreover, it
contains a copy
of every kcolored finite graph. We discuss some results
of Truss
concerning the cycle structure of automorphisms on R.
We also discuss
some of our results (joint with James Mitchell) concerning
approximations of automorphisms on R.

Wednesday, October 1^{st}, 2008
at
1:00pm NS 333
Distinct permutation sums modulo n
Professor Jake Wildstrom
University
of Louisville
Abstract:
Hunter Snevily conjectured that, for any sequence of k
numbers, there is a permutation of the set {1, 2, 3, ...,
k} such that
the termwise sum of the sequence and permutation yields
k distinct
values modulo n, as long as k < n. A secondary question,
posed by
Andre Kezdy, concens quantifying the number of different
permutations
which accomplish this goal. I will present both the established
results with regard to this problem and ongoing lines
of research.

Wednesday, September 24^{th}, 2008
at
1:00pm NS 333
Studies of Perfect Matchings in Bipartite
Graphs
Tim Brauch
University
of Louisville
Abstract:
This talk will have two related parts. The first part will
discuss using combinatorial nullstellensatz to find bounds
on the
number of perfect matchings in bipartite graphs. This
will be
accomplished using two tools, the discrete Fourier transform
on
abelian groups and matroid intersection. The second part
of the talk
will focus on newer material. In using combinatorial
nullstellensatz
it is important to create an appropriate function for
each instance.
In the second part I will use the coefficients of these
polynomials to
create vectors and discuss some of the properties that
can be derived
from the vector space spanned by the coefficient vectors.
The talk
will conclude with some open problems.
This is joint work with Andre Kezdy and Hunter Snevily.

Wednesday, March 26^{th}, 2008 at
1:00pm NS 333
The NIP Graph of a Social Welfare Function
Professor Lee Gibson
University
of Louisville
Abstract:
Here we consider the fraction of pairs of m distinct alternatives
on which a social welfare function f may be nondictatorially independent
and Pareto when the domain of f satisfies the free ktuple property.
When k=4 we improve the existing upper bound to 1/sqrt{m  1}}. When
there are at least 26 alternatives and k > m/2  1 we obtain an original
upper bound, {2(m + 2)}/{m(m + 1)}. To obtain these results we define and
analyze the graph formed from the nondictatorial independent and Pareto
pairs and combine the results of this analysis with known results from
extremal graph theory..

Wednesday, March 5^{th}, 2008 at
1:00pm NS 333
Introduction to Groebner bases  Part III
Professor André Kézdy
University
of Louisville
Abstract:
This last talk in the series shows several applications of Groebner
bases including: finding minimal polynomials in field extensions, graph
coloring, constructing random walks on fibres, and detecting hamiltonian
cycles in graphs.

Wednesday, February 27^{th}, 2008
at
1:00pm NS 333
Introduction to Groebner bases  Part II
Professor André Kézdy
University
of Louisville
Abstract:
This talk finally defines Groebner bases. We'll
discuss the multivariable version of the polynomial division algorithm,
Groebner bases, Buchberger's Scriterion, Hilbert's basis theorem
and nullstellensatz. If time permits, examples using Maple will be
presented.

Wednesday, February 20^{th}, 2008
at
1:00pm NS 333
Introduction to Groebner bases  Part I
Professor André Kézdy
University
of Louisville
Abstract:
This talk will develop the background that sets the stage
for the introduction of Groebner bases. We'll discuss polynomials,
ideals, varieties, the division algorithm, and monomial orderings.

Wednesday, January 30^{th}, 2008
at
1:00pm NS 333
Recent
results on unit barvisibility graphs
Ms. Lesley Wiglesworth
University
of Louisville
Abstract:
A unit barvisibility graph (UBVG) is a
bar visibiliy graph in which all bars have unit length. These graphs
were first introduced by Dean and Veytsel [DV]. The triangulated
polygons that are UBVGs have been characterized by Dean, Gethner,
Hutchinson [DGH]. In this talk, we will give two characterizations of
unit barvisibility graphs with a unit bar layout having width less
than two. One characterization is reflective of the layout, while
the other gives insight into an algorithm for testing whether or not
a graph has such a unit bar layout. Results will also be given on induced
subgraphs of grids.
[DV] A. Dean and N. Veytsel,
Unit barvisibility graphs, Congressus Numerantium 160 (2003), 161175.
[DHV] A. Dean, E. Gethner, and J. Hutchinson, Unit barvisibility
layouts of triangulated polygons: extended abstract, in Lecture
Notes in Computer Science 3383: Graph Drawing 2004, J. Pach (Ed.),
SpringerVerlag, Berlin (2004), 111121.

Wednesday, January 23^{rd}, 2008
at
1:00pm NS 333
Codes
over Finite Rings
Dr. JonLark Kim
University
of Louisville
Abstract:
Codes over finite rings, especially over Z_{4},
have been of great interest due to the seminal paper by Hammons Jr,
et. al.(1994). Some of their main results are that Kerdock and Preparata
codes are linear over Z_{4} via the Gray map from Z_{4}^{n}
to Z_{2}^{2n}, and that as Z_{4}codes they
are duals. Recently people have considered codes over finite chain
rings (e.g., Norton and Salagean (2000)) and codes over finite Frobenius
rings (e.g., Wood (1999)).
In this talk, we begin with a general introduction to coding
theory. Then we describe new recent results on MDS codes over finite
chain rings, and selfdual codes over finite chain rings including
Galois rings. This presentation is based on joint papers with S.T.
Dougherty, H. Kulosman, and Y. Lee.

Tuesday, November 20^{th}, 2007
at
12:00pm NS 333
Algebra
and computation
Professor Steve Seif
University
of Louisville
Abstract:
The algebraic theory of finite automata will be overviewed
no prerequisites.
More recent computational models will be described. Recent
results and
problems (some longstanding, most more recent) in the area
will be described..
All are welcome.

Thursday, November 15^{th}, 2007
at
12:00pm NS 333
(Note nonstandard meeting day!)
Online
Ramsey Theory
Kevin Milans
University
of Illinois at UrbanaChampaign
Abstract:
Online Ramsey theory is the study of a family of combinatorial
games between Builder and Painter. Starting with an infinite set
of independent vertices, Builder presents an edge to Painter. Painter
responds by coloring the edge red or blue. Builder continues to present
edges, and Painter colors each edge as it is presented. Builder's
goal is to obtain a monochromatic copy of some target graph G, and
Painter tries to stop Builder. Classic Ramsey theory shows that if
Builder is allowed to present large cliques, then Builder wins. Therefore,
we restrict Builder by requiring that at all times, the presented graph
belongs to a family of graphs H. This defines the game (G, H).
We examine such games in the case that H=S_k, where S_k
is the class of graphs with maximum degree at most k. For each graph G,
define the online degree Ramsey number odr(G) to be the minimum k such
that builder wins (G, S_k). We characterize the graphs G with odr(G) <=
3. If G is a cycle, then odr(G) <= 5. If in addition G is an even cycle,
a triangle, or a sufficiently large odd cycle, then odr(G) <= 4. We conclude
with some open problems.

Tuesday, October 23^{rd}, 2007 at
12:00pm NS 333
The
Secretary Problem; optimal stopping on complete bipartite graphs
with random cardinalities of partite sets
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Let G be a complete bipartite graph of order n, where n is odd. Assume
that the size of the larger partite set has the binomial distribution
with p =1/2. The vertices of G are coming in some random order and reveal
the structure of the induced graph. We want to stop on the current vertex
maximizing the probability that this vertex comes from the smaller partite
set. The optimal stopping strategy is presented with exact probabilities
of success
for each value of n.

Tuesday, October 16^{th}, 2007 at
12:00pm NS 333
Dynamic Location on Graphs
Professor Jake Wildstrom
University
of Louisville
Abstract:
I will be talking about problems dealing with
dynamic location on graphs: starting with a traditional problem dealing
with a resource relocating on a network in response to realtime service
requeststhroughout the network, I'll proceed to present generalizations
of the distance and cost functions, and an explanation of the computationalmethods
feasible for analyzing these more general problems, as well as
some preliminary results and plans for future study.

Tuesday, October 2^{nd}, 2007 at
12:00pm NS 333
Voting based upon two alternatives
Professor Robert Powers
University
of Louisville
Abstract:
This past summer, as part of the SROP program, Jonathan Perry and
I investigated axiomatic foundations of voting in the case of two
alternatives and a fixed number of voters. In this talk I will focus
on two axioms: anonymity and neutrality.

Tuesday, September 25^{th}, 2007
at
12:00pm NS 333
Upper
Bounds for the length of $s$ Extremal Codes over
$\mathbb
F_2$, $\mathbb F_4$, and $\mathbb F_2 + u\mathbb F_2$
Dr. Sunghyu Han
University
of Louisville
Abstract:
Our purpose is to find an upper bound for the length of $s$ extremal
codes over $\mathbb F_2$ (resp. $\mathbb F_4$) when $d \equiv 2 \pmod{4}$
(resp. $d$ odd). This question is left open in [E. P. Bautista et
al., s extremal additive $\mathbb F_4$ codes, Advances in Mathematics
of Communications, <>\textbf{1}, pp. 111 130, 2007] and [P.
Gaborit, A bound for certain s extremallattices and codes, preprint].
More precisely, we show that there is no $s$ extremal binary code of
length $n \ge 21d 82$ if $d >6$ and $d \equiv 2 \pmod{4}$. Similarly
we show that there is no $s$ extremal additive <>$\mathbb F_4$
code of length $n \ge 13d 26$ if $d>1$ and $d$ is odd.We also define
$s$ extremal self dual codes over $\mathbb F_2 + u\mathbb F_2$ and derive
an upper bound for the length of an $s$ extremal self dual code over $\mathbb
F_2 + u\mathbb F_2$ using the information on binary
$s$ extremal codes.
.

Tuesday, September 11^{th}, 2007
at
12:00pm NS 333
Monomial ideals of linear type
Professor Hamid Kulosman
University
of Louisville
Abstract:
We talk about monomial sequences that generate
ideals of linear type.

Tuesday, September 4^{th}, 2007
at
12:00pm NS 333
Open Problems
Professor André Kézdy
University
of Louisville
Abstract:
I will mention results and questions from the summer REGS
workshop that my students and I attended this past summer.

Wednesday, November 8^{th}, 2006
at
2:00pm NS 333
Generalized Secretary Problem on graphs  the
directed path case
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
The the classical secretary problem, 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. I will talk about the joint paper (with
Michal Morayne) in which we generalized the original problem to graphs
(digraphs) without any order structure.
I will present an optimal stopping time for directed path
of order n.

Wednesday, November 1^{st}, 2006
at
2:00pm NS 333
Generalized Secretary Problem on graphs  complete
bipartite graph case
Professor Ewa Kubicka
University
of Louisville
Abstract:
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. We generalize
the classical Secretary Problem to an optimal stopping problem on graphs
and directed graphs. The only structure of a set under consideration is
a graph (or digraph) 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.
I will talk about the joint paper (with Grzegorz Kubicki)  "How to
Choose Rarity" where the optimal stopping time was found for a complete
bipartite graph K(m, n) with unbalanced partite sets M and N, M >
N, and the aim set being the smaller partite set N.

Wednesday, October 25^{th}, 2006
at
2:00pm NS 333
Asymptotics of a class of directed word graphs
Professor Steve Seif
University
of Louisville
Abstract:
To a finite word w in an alphabet �� can be associated its socalled
alternation word digraph (AWD) Alt(w). In a broad sense AWDs are a
generalization of posets. AWDs will be motivated, defined and examples
will be presented. An asymptotic upper bound for the number of AWDs will
be presented and then used to show that the growth of the Perkins monoid
is sublogexponential. The focus will mainly be on the combinatorics
and several open problems will be presented.

Wednesday, October 11^{th}, 2006
at
2:00pm NS 333
Double circulant quadratic residue codes and
their generalization
Professor JonLark Kim
University
of Louisville
Abstract:
We overview double circulant quadratic residue codes andintroduce
their new generalization based on strongly regular graphs and doubly
regular tournaments. We conclude with some future research problems.
This is a joint work with Steven Dougherty and Patrick Sole.

Wednesday, September 20^{th}, 2006
at
2:00pm NS 333
When is it possible for a finite semimodular
lattice to contain a median that is not bounded above by the join
of the input elements?
Mr. Jeremy White
University
of Louisville
Abstract:
It is known that in a finite semimodular lattice the join
of
a profile of elements need not be an upper bound for the
set of medians
for that profile.
We shall present some preliminary results that show if a
semimodular
lattice is "not very tall," then the join of a given profile
of elements
does provide an upper bound for the set of medians for that
profile.

Wednesday, September 13^{th}, 2006
at
2:00pm NS 333
Twogenerated ideals of linear type
Professor Hamid Kulosman
University
of Louisville
Abstract: We talk about the conditions for twogenerated
ideals in commutative
rings to be of linear type. We give some applications.

Wednesday, September 6^{th}, 2006
at
2:00pm NS 333
Volume Doubling: A weighted graph example
Professor Lee Gibson
University
of Louisville
Abstract:
In my last talk to the combinatorics seminar,
we discussed the volume doubling property for graphs, and a class
of examples which exhibited this property  the Cayley graphs of
finitely generated groups for which the number of vertices in concentric
balls grows like a polynomial. In this lecture we will explore a weight
function on the vertices of the graph Z. With this weight function,
we consider the total weight of all the vertices in a ball instead of
just the number of vertices. We will show that volume doubling holds
for this weighted graph, even though the volume growth function is not
asymptotically polynomial (in contrast to what happens for Cayley Graphs).
If time allows, we will also consider a nonweighted analogue of this
example. Later this semester in the Analysis seminar, I will demonstrate
that a property of functions called a Poincarв‘ inequality also holds
for this example.

Tuesday, April
18^{th}, 2006 at
4:30pm NS 333
Unit Bar Visibility Graphs
Ms. Lesley Wiglesworth
University
of Louisville
Abstract:
I will introduce the concept of bar visibility
graphs (BVG's)and unit bar visibility graph (UBVG's), providing history
and motivation.
Some recent results by Alice Dean & Natalia Neytsel
on UBVG's
will be given as well as some open problems

Tuesday, March 7^{th}, 2006 at
4:30pm NS 333
Freespectra of algebras, with a counting problem
involving posets, Part II
Professor Steve Seif
University
of Louisville
Abstract:
Definitions and examples on the topic above will be reviewed.
Recent results on asymptotic classes of free spectra will
be presented,
along with a related counting problem for socalled generalized
posets.
All are welcome. No prerequisites.

Tuesday, February 21^{st}, 2006
at
4:30pm NS 333
Recent results in the freespectra problem for
algebras
Professor Steve Seif
University
of Louisville
Abstract:
I will describe a classical algebraic invariant, the free
spectum,
whereby to each finite algebra A is associated a sequence
of
positive integers (f_n(A)). In the talk the free spectrum
will be
defined and numerous examples given, including from basic
algebraic
structures such as groups and rings.
Some of the techniques for determing the asymptotics of
free spectra
have a combinatorics flavor: an open counting problem for
a class of
structures that generalize posets will be presented.
There are no prerequisites for the talk.

Tuesday, February 7^{th}, 2006 at
4:30pm NS 333
An open problem on connected matchings
Professor Andre Kezdy
University
of Louisville
Abstract:
I will
present the motivation, background, and
evidence
for a recent conjecture by Furedi, Gyarfas, and Simonyi
(Combinatorics,
Probability, and Computing (2005) 14, 435438).
A set of
pairwise disjoint edges M in a graph G is a connected matching
if, for
any pair of edges e and f in M, there exists an edge in G
incident
to both e and f. Furedi et al. conjecture that, every graph with
4t1 vertices
and whose complement contains no triangle must contain
a connected
matching with at least t edges. This bound, if true, would be
sharp as
seen by considering the graph that is the union of two
copies of the
complete graph on 2t1 vertices.

Tuesday,
November 29^{th}, 2005 at 1:30pm NS
234
INFINITE
GRAPHS, VOLUME GROWTH, AND CAYLEY GRAPHS OF GROUPS
Professor Lee Gibson
University
of Louisville
Abstract:
A natural sense of distance on any infinite graph
is the minimum number of edges
needed to form a path between two vertices. Using this
notion of distance, how does the number
of vertices inside a ball of a given radius depend on
the radius? The answer to this question, which
can come in a number of varieties, has important consequences
for the study of other topics relating
to infinite graphs. The Cayley graphs of finitely generated
groups form a class of graphs for which
the answer to this question is somewhat simple. In this
talk, we will consider a number of examples
which will assist us in understanding the volume growth
of infinite graphs – and especially the
Cayley graphs of groups.
Although several interesting and important results will
be mentioned, this talk will contain no
new research, and perhaps only one proof.

Tuesday,
November 15^{th}, 2005 at 1:30pm NS
234
Investigating
an upper bound for the set of medians in an upper
semimodular lattice  Part II
Mr. Jeremy White
University
of Louisville
Abstract:
For a modular lattice, the upper and lower bound
is well known. However, if the modular condition is weakened and replaced
by upper semimodularity, then the upper bound "drifts" away from the
upper bound that holds in the modular case.
Note: In this talk I plan to give a general introduction
to the question that I am working on for my dissertation research.
I hope to explain enough background lattice theory so that the audience
can get a basic idea about the question I am working on.

Tuesday,
November 8^{th}, 2005 at 1:30pm NS
234
Investigating
an upper bound for the set of medians in an upper
semimodular lattice  Part I
Mr. Jeremy White
University
of Louisville
Abstract:
For a modular lattice, the upper and lower bound
is well known. However, if the modular condition is weakened and replaced
by upper semimodularity, then the upper bound "drifts" away from the
upper bound that holds in the modular case.
Note: In this talk I plan to give a general introduction
to the question that I am working on for my dissertation research.
I hope to explain enough background lattice theory so that the audience
can get a basic idea about the question I am working on.

Tuesday,
November 1^{st}, 2005 at 1:30pm NS
234
Some
open problems on formally selfdual codes
Professor JonLark Kim
University
of Louisville
Abstract:
A binary
code is called formally selfdual (f.s.d.) if its weight enumerator
is the
same as its dual code. Formally selfdual codes have been of interest since
sometimes
they have
a larger minimum distance than selfdual codes of the same length.
An f.s.d.
code is called even if all weights of the codewords are even, and
odd otherwise.
In this
talk I will begin with basic definitions of f.s.d. codes
and describe
the current known status of classification of extremal/maximal
f.s.d. even codes.
I will
also describe a conjecture claiming that there does not exist a nearextremal
f.s.d. even code
whose length
is at least 48 and divisible by 8. This conjecture has been proposed
in our joint
paper with
Professor Vera Pless.

Tuesday,
October 17^{th}, 2005 at 1:30pm NS
234
A Survey
of Tree Labeling
Professor André Kézdy
University
of Louisville
Abstract:
I will give a brief survey of tree labelings.

Tuesday,
September 27^{th}, 2005 at 1:30pm NS
234
GRADED
ALGEBRAS ASSOCIATED TO AN IDEAL
Professor Hamid Kulosman
University
of Louisville
Abstract:
We will talk about some natural graded algebras
that can be associated to an ideal: Rees, tensor, symmetric, exterior.
They often serve as tools for investigation of various properties of
the ideal, like, for example, the relation type of the ideal. We will
talk about this property in more detail, present some recent results
and open questions.

Tuesday,
September 20^{th}, 2005 at 1:30pm NS
234
COLORINGS
OF RATIONAL POINTS OF UNIT DISTANCE GRAPHS
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
Partitioning the Euclidean nspace into minimal
number of sets in such a way that within one set no two points are
at unit distance apart is one of the best known problems of combinatorial
geometry. Using graph theory language, this problem can be expressed
as a coloring problem. In this talk we will investigate two types of colorings
of the rational points in nspace. In patch colorings, the colors occupy
open sets with parts of their boundaries. Rigid colorings are colorings
which uniquely extend from any nonempty open subset. The proof techniques
are from number theory.

Tuesday,
September 13^{th}, 2005 at 1:30pm NS
234
The number of times an
anonymous rule violates independence
in the 3by3 case
Professor Robert Powers
University
of Louisville
Abstract:
If an anonymous rule f
always outputs a transitive relation and satisfies Pareto,
then by Arrow's theorem, f violates the condition of independence.
We give lower and upper bounds
for the number of times an anonymous rule violates independence
in the case of 3 alternatives
and 3 voters.

Wednesday,
March 30^{th}, 2005 at 1pm NS 234
Some Open Problems on
Graphs, Permanents, and Tree Packing
Professor André Kézdy
University
of Louisville
Abstract:
I will introduce several
open problems in the hopes of sparking interest in some collaborative
work.

Wednesday,
March 2^{nd}, 2005 at 1pm NS 234
Ternary Representations
of Hierarchies
Professor Robert Powers
University
of Louisville
Abstract:
A hierarchy is a special
type of hypergraph usually seen in the theory of classification.
I will talk about some of my current research on representing hierarchies
from the point of view of ternary relations.

Wednesday,
February 16^{th}, 2005 at 1pm NS 234
Introduction to Free
Spectra of Finite Groups & Algebras
Professor Steve Seif
University
of Louisville
Abstract:
Given
a finite group G, for a positive integer n, the positive integer fnG is the number of distinct functions
from Gn → G which
can be represented by words in the alphabet {x1,...,xn}. There are only GG^G functions of nvariables from G to itself; so fnG <= GG^G. A small example: let G be the two element Boolean group. Since G satisfies x2 = 1 and, for all i and j, we have xi xj = xj xi,
it's not difficult to see that there are exactly 2n distinct functions represented by
the words in n variables; that is,
fnG = 2n.
In
the 1960's, G. Higman and B.L. Neumann proved that there exists
a positive real d and a positive integer k such that the sequence (fnG)n=1,2,... is eventually bounded by 2dn^k if and only if G is nilpotent of class k or less. They
prove that if G is not nilpotent, then the growth of fnG is logexponential  meaning that there exists a positive
constant c such that fnG is eventually greater than 22^cn. The HigmanNeumann result indicate that the asymptotic
growth of (fnG)
is an indicator of the properties of the group.
The following is a longstanding open problem: Determine
all possible asymptotic growth rates of (fnA),
as A ranges over all finite algebras. A
short history of the problem along with some recent advances will
be presented. Related problems and their connections to computer science
will be discussed.

Wednesday,
February 2^{nd}, 2005 at 1pm NS 234
Title: Secretary Problem
different versions, different optimal strategies, different probabilities
of success
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
The classical secretary problem is the following
online decision problem: n elements (candidates for a job of a secretary)
which are linearly ordered from the worst to the best are observed
one by one in some random permutation. Knowing only the relative
ranks of the candidates examined so far, we want to stop the process
by picking the presently observed candidate maximizing the probability
of selecting the best candidate. Two other versions of the problem,
one for partial order and the other for directed path without order
structure are examined. Surprisingly, the optimal are completely different
for these three versions as well as probabilities of success.

Wednesday,
January 19^{th}, 2005 at 1pm NS 234
Title: Listening for
perfect matchings in bipartite graphs
Professor André Kézdy
University
of Louisville
Abstract:
To apply successfully the "combinatorial nullstellensatz'"
technique, one must find a nonzero coefficient in a multivariate polynomial
 a nontrivial task typically. These coefficients can be viewed
as frequencies to which one can listen for the presence of a combinatorial
object. To hone the method to find such noisy frequencies, the problem
of detecting (via this technique) a perfect matching in a bipartite
graph  a well known "easy" problem  was chosen as a prototype.
I will mention a fast algorithm to listen for these perfect
matchings in bipartite graphs using matroid intersection. Other
related problems, some open, will also be mentioned.

