

Algebra, Combinatorics, and Number Theory Seminar
Wednesday,
November 19^{th},
2014 at
1:00pm NS 212F
Stability questions on Hiraguchi's inequality
Professor Csaba Biro
University
of Louisville
Abstract:
Hiraguchi's Theorem states that the dimension of a poset does not
exceed half of the number of elements. What if the dimension is just slightly
less than this upper bound? Depending on what "slightly less" means, we
get different answers. We survey recent results on this topic.
(Joint work with Peter Hamburger, Attila Por, and William T. Trotter.)

Past Seminars...
Wednesday,
October 8^{th},
2014 at
1:00pm NS 212F
LaTeX Seminar
Charlie Suer
University
of Louisville
Abstract:
LaTeX is one of the most important way mathematicians
communicate their ideas in writing, so it is something all math graduate
students and faculty should be familiar with. For convenience, we will use
the online LaTeX service at sharelatex.com. We will cover the basics of
getting started in a simple document including common commands and environments.
We will also talk about how to create your own custom commands (macros) and
get a glimpse into why this is powerful and important. Finally, we will
discuss some features that may be of interest to faculty including tikz (for
drawing pictures) and beamer (for making presentations). Feel free to bring
your laptop to follow along.

Wednesday,
October 1^{st},
2014 at
1:00pm NS 212F
Reconstruction Problems in Graphs
Professor Ortrud Oellermann
University
of Winnipeg
Abstract:
We say that a graph can be reconstructed from partial
information about its structure if the graph can be uniquely determined from
this information. We begin by giving an overview of graph reconstruction problems.
In the second part of the talk we consider the problem of reconstructing a
graph from its digitally convex sets; where a set of vertices S is digitally
convex if every vertex, whose closed neighbourhood is contained in S, also
belongs to S.

Wednesday,
September 10^{th}, 2014 at
1:00pm NS 212F
Professor Jinjia Li
University
of Louisville
Abstract:
Given a boundedabove free complex over a CohenMacaulay
ring such that the homology are of finite length, we describe a construction
which connects its homology to that of another complex with fewer nonvanishing
homology. A recent embedding theorem of Hochster and Yao plays a crucial
role in this construction. Some further applications of this construction
will be discussed. This is joint work with Y. Yao.

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.

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.

