

Algebra, Combinatorics, and Number Theory Seminar
Wednesday, March 1^{st}, 2017 at 3pm NS 212C
Fine grained complexity of coloring unit disks
Professor Csaba Biro
University
of Louisville
Abstract: Many classical hard algorithmic problems on graphs, like coloring, clique number, or the
Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms
of time complexity $2^{O(\sqrt{n})}$. We study the coloring problem of unit
disk intersection graphs, where the number of colors is part of the input.
We conclude that, assuming the Exponential Time Hypothesis, no such speedup
is possible. In fact we prove a series of lower bounds depending on further
restrictions on the number of colors. Generalizations for other shapes and
higher dimensions were also achieved.
Joint work with E. Bonnet, D. Marx, T. Miltzow, and P Rzazewski.

Past
Seminars...
Wednesday, April 20^{th}, 2016 at 10:00am NS 212F Finding detours and Gallai vertices in distancehereditary graphs
Professor André Kézdy
University
of Louisville
Abstract: A
detour of a graph is a path of maximum length. A vertex that is common to
all detours of a graph is called a Gallai vertex. Many graphs do not have
Gallai vertices. But there are several (still open) conjectures asserting
that certain types of graphs have a Gallai vertex. Last November I presented
a proof (in this seminar) that dually chordal graphs have a Gallai vertex,
thereby resolving conjectures concerning the wellstudied doubly chordal
and strongly chordal graphs. In this talk I will present ongoing work to
resolve this question for distancehereditary graphs.
This is joint work with Adam Jobson.

Wednesday, April 11^{th}, 2016 at 10:00am NS 212F Conditions for Cyclic RoundRobin Tournaments
Professor Daniel SmithTone
University
of Louisville
Abstract: Imagine
a tournament of the board game RISK. Suppose that there are 7 players and
each game involves 3 players. The set, S, of players as well as a collection
of subsets B of S with the property that the size of every element in B is
three and every pair of players is contained in exactly one element of B
is a roundrobin tournament. In particular, this means that every player
plays against every opponent exactly once. Such a tournament is a roundrobin
tournament. A tournament is cyclic if there exists a permutation p of S
such that p=S and p is Binvariant.
We derive an algebraic means of showing the existence of such tournaments.

Wednesday, March 23^{rd}, 2016 at 10:00am NS 212F Path Intersection Graphs
Adam Jobson
University
of Louisville
Abstract:
Path intersection graphs are families of graphs that generalize line graphs.
A graph G is a P(n,k)graph if there is a collection of nvertex paths such
that every vertex of G corresponds to a distinct path and two vertices of
G are adjacent if and only if the corresponding paths intersect in at least
a kvertex path. The traditional line graphs are exactly the P(2,1)graphs.
Several researchers have proposed that other P(n,k)graph families should
have characterizations analogous to one or more of the wellknown characterizations
of line graphs. A couple of summers ago, André Kézdy, Levi Sledd (an undergraduate
from Centre), and I proved that many P(n,k)graph families have an infinite
number of minimal forbidden induced subgraphs, thereby dashing the hope of
a Beinekestyle finite forbidden subgraph characterization. Despite that,
we also showed some of those same families do have other characterizations
that mirror the line graph case.
In this talk I will give an overview of some of the many characterizations
of line graphs, describe the valid analogs for P(n,k)graphs, and discuss
how those can be used to prove that some P(n,k)graph families have an infinite
number of minimal forbidden induced subgraphs. Time permitting, I will also
examine the known relationships between the various families of path intersection
graphs and highlight some of the (numerous!) unsolved problems in this area.

Wednesday, March 2^{nd}, 2016 at 10:00am NS 212F Tinkering with May’s Theorem
Professor Robert Powers
University
of Louisville
Abstract:
In 1952, May proved that simple majority rule is the only voting rule satisfying
the axioms of anonymity, neutrality, and strong monotonicity. Anonymity implies
that the identity of the voters is not used when determining the winner of
an election. Neutrality means that the winning outcome does not depend on
the labeling of the two candidates. Finally, strong monotonicity implies
that if the outcome of an election is a tie and one or more individuals change
their vote(s) to candidate X while everyone else votes the same way, then
X should be the winner of the new election. In this talk, I will show what
happens when one tinkers with the axiomatic structure of May’s Theorem.

Wednesday, February 17^{th}, 2016 at 10:00am NS 212F On the Differential Security of the HFEv^{} Signature Primitive
Jeremy Vates
University
of Louisville
Abstract: Multivariate
Public Key Cryptography (MPKC) is one of the most attractive postquantum
options for digital signatures in a wide array of applications. The history
of multivariate signature schemes is tumultuous, however, and solid security
arguments are required to inspire faith in the schemes and to verify their
security against yet undiscovered attacks. The effectiveness of "differential
attacks" on various fieldbased systems has prompted the investigation of
the resistance of schemes against differential adversaries. Due to its prominence
in the area and the recent optimization of its parameters, we prove the security
of HFEv against differential adversaries. We investigate the newly suggested
parameters and conclude that the proposed scheme is secure against all known
attacks and against any differential adversary.

Wednesday, Feb 10^{th}, 2016 at 10:00am NS 212F Informal Introduction to HFEv^{} Scheme and Differential Attacks
Professor Daniel SmithTone
University
of Louisville
Abstract: Introduction to differential security arguments for the new digital encryption scheme Gui.

Wednesday, January 27^{th}, 2016 at 10:00am NS 212F An Asymptotically Optimal Structural Attack on the ABC Multivariate Encryption Scheme
Professor Daniel SmithTone
University
of Louisville
Abstract: Historically,
multivariate public key cryptography has been less than successful at offering
encryption schemes which are both secure and efficient. At PQCRYPTO '13
in Limoges, Tao, Diene, Tang, and Ding introduced a promising new multivariate
encryption algorithm based on a fundamentally new idea: hiding the structure
of a large matrix algebra over a finite field.
In earlier work, a subset of the authors defined a differential invariant,
an analogue of a subspace left invariant under the action of a collection
of linear operators. While this notion has proven useful in computationally
detecting, within nonlinear systems of functions, linear actions on subspaces
of the domain, the idea is not immediately applicable in the setting of the
ABC scheme. Instead, we generalize the concept, defining a subspace differential
invariant capable of extracting linear actions on subspaces of the span of
a system of nonlinear functions.
We show that subspace differential invariants are inherent to the ABC methodology,
and that their computation is feasible. Our attack is a structural key recovery
attack (thus the entire system, instead of a single message, is undermined)
which is asymptotically optimal among all known attacks on the original scheme
and its generalizations. We also discuss how the complexity of the attack
uniquely determines the structure of the formulae in the ABC scheme.

Wednesday, December 2^{nd}, 2015 at 3:00pm NS 212D Characterization of a Class of Majority Rules on an Infinite Population
Sarah King
University
of Louisville
Abstract: May
(1952) was able to characterize simple majority rule with three axioms: Strict
Monotonicity, Anonymity, and Neutrality. Through a relaxation on the Monotonicity
condition, Llamazares (2006) characterized a class of majority rules. Through
an examination of the role of anonymity in May's Theorem, we will look at
how we can extend Llamazares' results on this class of majority rules from
a finite population to an infinite population. Characterizing such rules
on an infinite population requires we consider different levels on anonymity
as well as introduce a new axiom to prevent triviality.

Wednesday, November 18^{th}, 2015 at 3:00pm NS 212D Detour Trees
Professor André Kézdy
University
of Louisville
Abstract: A detour of a graph is a path of maximum length. A vertex that is common
to all detours of a graph is called a Gallai vertex. We introduce the notion
of a detour tree, a spanning tree of a graph in which the vertex set of any
detour (of the graph) induces a subtree. We use detour trees to prove that
any connected dually chordal graph has a Gallai vertex. Consequently connected
graphs from subfamilies of dually chordal graphs have a Gallai vertex, including
the wellstudied doubly chordal, strongly chordal and interval graphs. Separately
we prove that connected cographs (which are not necessarily dually chordal)
have a Gallai vertex. Analogous results for cycles of maximum length follow.
We also characterize graphs that have a detour tree. Several open problems
will be mentioned.
This is joint work with Adam Jobson, Jeno Lehel, and Susan White.

Wednesday, November 11^{th}, 2015 at 3:00pm NS 212D Fthresholds in commutative ring theory
Professor Jinjia Li
University
of Louisville
Abstract: For
a commutative Noetherian ring (with unity) of prime characteristic p, one
can define a numerical invariant of an ideal, know as the Fthreshold, via
comparing the (regular) powers and the Frobenius powers of the ideal. This
invariant, as a characteristic p analog of the concept of log canonical threshold
introduced in birational geometry, had been studied intensively in recent
years. After introducing this concept, we will demonstrate some simple examples
in which this invariant can be computed in an elementary fashion. We will
also discuss an inequality on Fthreshold, which was initially conjectured
by Watanabe and Yoshida, and some new observations related to this.

Wednesday, October 27^{th}, 2015 at 3:00pm NS 212D Characterization of Uniquely Pressable Graphs
Professor D. Jacob Wildstrom
University
of Louisville
Abstract: Hannenhali and Pevzner identified the number of reversals
necessary to sort signed permutations with actions performed on an associated
twocolored graph. These "pressing actions", which alter the colors
and adjacencies in the graph, bear a certain resemblance to the classic
"lightsout" puzzle. Recent work of Cooper and Davis seeks to
characterize graphs which have a successful pressing sequence, investigating
computational techniques and the computational complexity of finding pressing
sequences for arbitrary graphs. A question they leave open is the
characterization of those graphs which are uniquely pressable, i.e., those
which have a unique successful sequence of presses.
This presentation will exhibit three means by which
uniquely pressable graphs can be compleltely enumerated; in addition these
generative processes will show that both testing a graph for unique
pressability and determining its unique pressing sequence can be completed in
polynomial time. This is joint work with Adam Jobson.

Wednesday, October 20^{th}, 2015 at 3:00pm NS 212D Ryann Cartor, Ryan Gipson, Jeremy Vates
University
of Louisville
Abstract: Multivariate Public Key Cryptography (MPKC) is one of the
most attractive postquantum options for digital signatures in a wide array of
applications. The history of multivariate signature schemes is tumultuous,
however, and solid security arguments are required to inspire faith in the
schemes and to verify their security against yet undiscovered attacks. The
effectiveness of ``differential attacks'' on various fieldbased systems has
prompted the investigation of the resistance of schemes against differential
adversaries. Due to its prominence in the area and the recent optimization of
its parameters, we prove the security of HFE against differential
adversaries. We investigate the newly suggested parameters and conclude that
the proposed scheme is secure against all known attacks and against any
differential adversary.

Wednesday, October 7^{th}, 2015 at 3:00pm NS 212D Some applications of the asymmetric version of the Lovasz Local Lemma,
Part II
Professor Csaba Biro
University
of Louisville
Abstract: Today we will see three applications of the local lemma.
We start with improving the lower bound (from last week) on diagonal Ramsey
numbers, then we discuss a lower bound for offdiagonal Ramsey numbers. We finish
the talk by showing the existence of certain posets that give lower bound for a
certain poset stability question. *It will be possible to understand today's talk
without the attendance of last week's talk.*

Wednesday, September 30^{th}, 2015 at 3:00pm NS 212D Some applications of the asymmetric version of the Lovasz Local Lemma,
Part I
Professor Csaba Biro
University
of Louisville
Abstract:
If we have finitely many pairwise independent
events, all
of which have positive probability, then obviously, the probability
that all
events hold simultaneously is positive. The celebrated Lovasz Local
Lemma
states (roughly speaking) that if the dependence among the events is
not too extensive, and the probability of each is fairly large, then
the same
conclusion holds. In this talk we prove the lemma, and show a classical
application to bound offdiagonal Ramsey numbers from below. If time permits, we mention some recent application by
the speaker to show the existence of certain posets with high dimension but low
Snumber.

Friday, April 10^{th}, 2015 at
10:00am NS 212F
The Mathematics of QuantumResistant Cryptography,
Part III
Professor Daniel SmithTone
University
of Louisville
Abstract:
We explore the current public key landscape, discussing some of the applications
of publickey cryptography. Several basic cryptographic notions are presented,
some abstract, some including concrete algorithms.

Friday,
March 27^{th}, 2015 at
10:00am NS 212F
The Mathematics of QuantumResistant Cryptography,
Part II
Professor Daniel SmithTone
University
of Louisville
Abstract:
We explore the current public key landscape, discussing some of the applications
of publickey cryptography. Several basic cryptographic notions are presented,
some abstract, some including concrete algorithms.

Friday,
February 27^{th}, 2015 at
10:00am NS 212F
The Mathematics of QuantumResistant Cryptography,
Part I
Professor Daniel SmithTone
University
of Louisville
Abstract:
We explore the current public key landscape, discussing some of the applications
of publickey cryptography. Several basic cryptographic notions are presented,
some abstract, some including concrete algorithms.

Wednesday,
December 3^{rd}, 2014 at
1:00pm NS 212F
Secretary problem and its generalizations for
partial orders, graphs, and digraphs.
Professor Grzegorz Kubicki
University
of Louisville
Abstract:
The secretary problem is a famous, more than 50 years old, problem
of the optimal stopping theory. In the classical secretary problem, there
are n linearly ordered objects, applicants for a secretary position. They
come for an interview in a random permutation (all permutations are equally
likely) and during the interview we can rank the applicants interviewed
so far. The decision about each applicant has to be made immediately after
the interview; once rejected, an applicant cannot be recalled. Because of
the last assumption, the problem is also called the marriage problem. Our
goal is to find a stopping rule that will maximize the probability of selecting
the best applicant. We will justify shortly the optimal strategy that tells
us to reject roughly the first n/e applicants and then stopping on the first
applicant who is better then all interviewed so far.
Among many generalizations of the problem, we will concentrate
on those in which the assumption about linear order of applicants is relaxed.
About 15 years ago, the secretary problem was defined for partial orders
with the goal to stop on a maximal element. Optimal stopping time was found
for posets whose Haase diagram were complete binary trees (Morayne), and
universal efficient algorithm was constructed for the situation when only
the number of objects is given to the selector without the knowldge of the
partial order itself (Preater).
In 2005, Kubicki and Morayne generalized the problem to graphs and digraphs,
where after each “interview” the graph (digraph) induced by the vertices
observed so far is known. Our goal is to find a stopping rule that will maximize
the probability of selecting a vertex from some predefined aim set A. Optimal
stopping time was found for directed path with A being an endvertex. We
have to be very patient in that case, since the stopping rule tells us to
wait as long as possible and stop only if there is no chance for the endvertex
to come later. Other sparse graphs, as well as powers of directed path,
were examined lately. Optimal stopping time was determined for complete
bipartite graphs with A being the smaller partite set, but in this case
we will use a language of urn scheme with balls in two colors. Finally,
two related results about universal efficient algorithms for digraphs with
A being the set of sinks are discussed.

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.)

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.

