Search
Main News Research Grad Courses Jobs Archives
Department People Undergrad
 


Algebra, Combinatorics, and Number Theory Seminar

Wednesday, April 16th, 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 non-linear functional equation
f(pr,qs) + f(ps,qr) = g(p,q) h(r,s)
for all  p, q, r, s in G. I will give several examples related to a specific case of the linear equation.

Past Seminars...
Wednesday, April 9th, 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 2nd, 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 Lp 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 26th, 2014 at 10:00am NS 212F
The chordal graph homomorphism problem - Part II
Professor Steve Seif
University of Louisville

Abstract: Chordal graphs are interesting; semi-lattices are semi-interesting, 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 polynomial-time 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 chalk-and-talk, self-contained discussion. All are welcome.

Wednesday, March 19th, 2014 at 10:00am NS 212F
The chordal graph homomorphism problem - Part I
Professor Steve Seif
University of Louisville

Abstract: Chordal graphs are interesting; semi-lattices are semi-interesting, 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 polynomial-time 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 chalk-and-talk, self-contained discussion. All are welcome.

Wednesday, March 5th, 2014 at 10:00am NS 212F
The ABC Matrix Scheme of Ding
Professor Daniel Smith-Tone
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 19th, 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 non-dictatorial, 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 quasi-orders, 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 12th, 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 29th, 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 15th, 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 4th, 2013 at 1:00pm NS 212D
Dealing with Hamiltonian cycles
Jeno Lehel
Visiting Scholar, University of Louisville

Abstract:  As a "Hamiltonian cycle non-expert" 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 20th, 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 Meta-Conjecture 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 Meta-Conjectures are explained and it is shown what fruit these have borne over the years. Also some possibilities for open problems are discussed.


Wednesday, November 6th, 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 30th, 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 minor-closed family, yet the finite list of minor-minimal apex obstructions remains unknown. We have recently determined all minor-minimal 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 minor-minimal 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 23rd, 2013 at 1:00pm NS 212D
Partition adjacency matrices
Eva Czabarka
University of South Carolina

Abstract:  Havel-Hakimi 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 16th, 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 NP-complete for general graphs and even for general bipartite graphs, but the problem is polynomial-time solvable for chordal graphs (graphs with no induced cycle of length greater than three). We show that the problem is polynomial-time 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 9th, 2013 at 1:00pm NS 212D
Extending the PC-Tree Algorithm to the Torus
Charlie Suer
University of Louisville

Abstract: Planar graphs have been well studied and there are many linear-time algorithms for determining if a given graph is planar.  In particular, we take a detailed look at the PC-Tree Algorithm of Shih and Hsu.  The torus and toroidal graphs are less understood, so we present an extension of the PC-Tree 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 25th, 2013 at 1:00pm NS 212D
I-adic completions of modules over commutative rings
Hamid Kulosman
University of Louisville

Abstract: I-adic completions of modules over Noetherian commutative rings are well-behaved, 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 18th, 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 k-COL, k-SAT,  H-COL (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 NP-complete. 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 4th, 2013 at 1:00pm NS 212D
Pathwidth and dimensions
Csaba Biro
University of Louisville

Abstract: The old-time 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 17th, 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 10th, 2013 at 2:30pm NS 212D
Acyclic and Indifference-Transitive 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, indifference-transitive 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 3rd, 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 27th, 2013 at 2:30pm NS 212D
Efficiency of limited-knowledge relocation of high-mobility and low-mobility resources

Professor Jake Wildstrom
University of Louisville

Abstract: Relocation of service-providers in response to changing real-time needs is suboptimal due to limited foreknowledge of client requests. Simple cost schedules for relocation and remote-service provision have been investigated both for the possibility of complete optimizability and the degree of inefficiency introduced by imperfect future knowledge. Traditionally, relocation and remote-service 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 "high-mobility", "medium-mobility", and "low-mobility". High-mobility resources have trivial optimization, and medium-mobility resources exhibit difficult-to-characterize behavior, but most real-world applications involve low-mobility resources, which have, in many cases, a surprisingly straightforward characterization.

Wednesday, March 20th, 2013 at 2:30pm NS 212D
Online Linear Discrepancy of Partially Ordered Sets

Professor Mitchel T. Keller
University of Nebraska-Lincoln

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 6th, 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 sixty-year-old 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. 23rd, 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. 27th, 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 k-tuple 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. 13th, 2012 at 10:00am NS 212D
Spectral Graph Theory and the Alon-Boppana 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 Alon-Boppanna bound on the spectrum and its recent generalizations.

Tuesday, Oct. 23rd, 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 vertex-transitive 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 Harris-Kesten Theorem from 1980 established the critical probability to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Oct. 16th, 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 vertex-transitive 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 Harris-Kesten Theorem from 1980 established the critical probability to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Oct. 2nd, 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 vertex-transitive 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 Harris-Kesten Theorem from 1980 established the critical probability to be 1/2, finally settling 20+ year old conjecture.

Tuesday, Sept. 25th, 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 k-tuple 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. 12th, 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. 4th, 2012 at 10:00am NS 212D
Explorations into the maximum length of Hajnal's Triangle-Free Game

Professor Jake Wildstrom
University of Louisville

Abstract: Hajnal proposed a game where two players successively add edges to an initially-empty triangle-free graph on n vertices until no more edges can be added without violating the triangle-free 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. 28th, 2012 at 10:00am NS 212D
The uniform attachment process

Professor Csaba Biro
University of Louisville

Abstract: Consider a sequence of non-negative 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,i-1\} 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 Erdos-Renyi infinite graph (aka Rado graph), and it should be accessible to even beginning graduate students.

Joint work with Udayan B. Darji.

Wednesday, April 18th, 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 11th, 2012 at 2:00pm NS 212D
A New Class of Linear Codes for Cryptographic Uses

Professor Jon-Lark 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 self-dual 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 Varshamov-Gilbert 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 4th, 2012 at 2:00pm NS 212D
3-connected $\{K_{1,3}, P_9\}$-free Graphs are Hamiltonian Connected

Paul Wrayno
Western Kentucky University

Abstract: We show that any graph that is 3-connected 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 hamiltonian-type 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 28th, 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 21st, 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 7th, 2012 at 2:00pm NS 212D
On-line 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 on-line 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 15th, 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 worst-case 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=n-1). 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 7th, 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 30th, 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 16th, 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 10-15 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, Kezdy-Snevily conjecture, Dasgupta-Karolyi-Serra-Szegedy 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 k-element 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 9th, 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 26th, 2011 at 2:00pm NS 212D
Diagonal F-threshold, Hilbert-Kunz 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 F-threshold  (i.e, the F-threshold of m with respect to an m-primary ideal I) is known to exists as  a real number in either the F-pure on the punctured spectrum case or in the  standard-graded complete intersection case. In this talk, we make connections between  the rationality of this invariant with that of the Hilbert-Kunz multiplicity by  investigating the socle degrees distribution of the Artinian quotient of R (modulo the  Frobenius powers).

Wednesday, October 19th, 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 ideal--a subideal called the core.  We introduce  the core of an ideal, whose study is motivated by the study of blow-up  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 12th, 2011 at 2:00pm NS 212D
Optimum Distance Profiles of Binary Self-Dual Codes


Finley Freibert
University of Louisville

Abstract: Self-dual codes have widespread relations to various areas such as combinatorial designs, unimodular lattices, and  group theory. A self-dual code is called {\em doubly-even}
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_{k-1}$ is called a {\em subcode  chain}, where the dimension of $C_i$ is $k-i$ for $i=0,
\dots k-1$. 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_{k-1}$ is called  a {\em distance profile} of $C$. Luo, Vinck, and Chen (2010)
have studied the optimum distance profiles of Reed-Solomon codes, Golay codes, the first order Reed-Muller codes, and the second order Reed-Muller 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 Jon-Lark Kim.


Wednesday, October 5th, 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 Palfy-Pudlak result brought the finite group theory community into the chase. The speaker will provide all definitions, along with examples, outline the Palfy-Pudlak result, and describe the current status of the question.

As is the case with some long-standing 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 21st, 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 Algebra-Combinatorics 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 Cohen-Macaulayness (Cohen-Macaulay rings and Cohen-Macaulay modules). 

Wednesday, September 14th, 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 Li-Yorke 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 self-map of the Cantor space.

Wednesday, September 7th, 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 24th, 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 long-standing problem 
seeking a characterization of the so-called 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 long-standing, 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 NP-complete problem as determined by the algebraic structure of finite universal algebras.  All are welcome.  Grad students are especially welcome.


Thursday, February 17th, 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 Alexandrov--Fenchel inequalities for mixed volumes to prove that this sequence is log-concave, i.e., $h_i(x)h_{i+2}(x)\le h_{i+1}^2(x)$ for $1\le i\le n-2$. 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 30th, 2010 at 1:30pm NS 317
Stack Domination Density
Professor Jake Wildstrom
University of Louisville

Abstract: Vizing's conjecture presents one of the most well-known 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 domination-density effects of substituting other families of graph for the path and the cycle as the underlying stack shape.

Tuesday, November 9th, 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 2nd, 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 26th, 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 19th, 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 5th, 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 28th, 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 3-cycles.

Tuesday, September 14th, 2010 at 1:30pm NS 317
The 2-distance coloring of the Cartesian product of cycles
using optimal Lee codes

Professor Jon-Lark 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 k-distance 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 k-distance 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 Seog-Jin Kim

Tuesday, August 31st, 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 21st, 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 so-called Combinatorial Nullstellensatz by Alon. We will talk about the proofs of that statement and applications to other areas.

Wednesday, March 24th, 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 G-V  bound, and the Singleton bound for codes in the finite-field Grassmannian. In this talk, we overview recent developments of these codes.  This is a joint work with Jon-Lark Kim.

Wednesday, February 10th, 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 20th, 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 17th, 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 sorting-pairs-in-bins problem, an anti-permanent conjecture, and Rado's conjecture. Different parts  of this talk are joint work with Adam Jobson, Hunter Snevily and Susan White.

Wednesday, April 15th, 2009 at 1:30pm NS 333
Properties of c-sequences
Professor Hamid Kulosman
University of Louisville

Abstract: The notion of a d-sequence 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 c-sequence is in turn a generalization of the notion of a d-sequence. Like regular and d-sequences, c-sequences 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 c-sequences and compare them with analogous properties of d-sequences. We will raise several questions.

Wednesday, March 4th, 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 19th, 2008 at 1:00pm NS 333
Introduction to lattices from codes
Professor Jon-Lark Kim
University of Louisville

Abstract:   There has been a remarkable connection between codes and
lattices, in particular, between self-dual 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_4-lifts 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 12th, 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 5th, 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 u-v 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 22nd, 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 15th, 2008 at 1:00pm NS 333
Approximations of automorphisms on the k-colored random graph - Part II
Professor Udayan Darji
University of Louisville

Abstract:   In this talk we discuss basic properties of the k-colored
random graph R.  In particular, we show that algebraically speaking,
the k-colored random graph is unique and, moreover, it contains a copy
of every k-colored 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 8th, 2008 at 1:00pm NS 333
Approximations of automorphisms on the k-colored random graph - Part I
Professor Udayan Darji
University of Louisville

Abstract:   In this talk we discuss basic properties of the k-colored
random graph R.  In particular, we show that algebraically speaking,
the k-colored random graph is unique and, moreover, it contains a copy
of every k-colored 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 1st, 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 24th, 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 26th, 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 k-tuple 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 5th, 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 27th, 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 S-criterion, Hilbert's basis theorem and nullstellensatz. If time permits, examples using Maple will be presented.

Wednesday, February 20th, 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 30th, 2008 at 1:00pm NS 333
Recent results on unit bar-visibility graphs
Ms. Lesley Wiglesworth
University of Louisville

Abstract: A unit bar-visibility 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 bar-visibility 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 bar-visibility graphs, Congressus Numerantium 160 (2003), 161-175.
[DHV] A. Dean, E. Gethner, and J. Hutchinson, Unit bar-visibility layouts of triangulated polygons: extended abstract, in Lecture Notes in Computer Science 3383: Graph Drawing 2004, J. Pach (Ed.), Springer-Verlag, Berlin (2004), 111-121.




Wednesday, January 23rd, 2008 at 1:00pm NS 333
Codes over Finite Rings
Dr. Jon-Lark Kim
University of Louisville

Abstract: Codes over finite rings, especially over Z4, 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 Z4 via the Gray map from Z4n to Z22n, and that as Z4-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 self-dual 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 20th, 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 15th, 2007 at 12:00pm NS 333
(Note non-standard meeting day!)
On-line Ramsey Theory
Kevin Milans
University of Illinois at Urbana-Champaign

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 23rd, 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 16th, 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 2nd, 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 25th, 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 11th, 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 4th, 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 8th, 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 1st, 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 25th, 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 so-called 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 sub-logexponential. The focus will mainly be on the combinatorics and several open problems will be presented. 

Wednesday, October 11th, 2006 at 2:00pm NS 333
Double circulant quadratic residue codes and their generalization
Professor Jon-Lark 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 20th, 2006 at 2:00pm NS 333
When is it possible for a finite semi-modular 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 13th, 2006 at 2:00pm NS 333
Two-generated ideals of linear type
Professor Hamid Kulosman
University of Louisville

Abstract: We talk about the conditions for two-generated ideals in commutative
rings to be of linear type. We give some applications.

Wednesday, September 6th, 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 non-weighted 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 18th, 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 7th, 2006 at 4:30pm NS 333
Free-spectra 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 so-called generalized posets.
All are welcome. No prerequisites.

Tuesday, February 21st, 2006 at 4:30pm NS 333
Recent results in the free-spectra 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 7th, 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, 435-438).
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
4t-1 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 2t-1 vertices.

Tuesday, November 29th, 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 15th, 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 8th, 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 1st, 2005 at 1:30pm NS 234
Some open problems on formally self-dual codes
Professor Jon-Lark Kim
University of Louisville

Abstract: 
A binary code is called formally self-dual (f.s.d.) if its weight enumerator
is the same as its dual code. Formally self-dual codes have been of interest since sometimes
they have a larger minimum distance than self-dual 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 near-extremal 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 17th, 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 27th, 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 20th, 2005 at 1:30pm NS 234
COLORINGS OF RATIONAL POINTS OF UNIT DISTANCE GRAPHS
Professor Grzegorz Kubicki
University of Louisville

Abstract: Partitioning the Euclidean n-space 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 n-space. 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 13th, 2005 at 1:30pm NS 234
The number of times an anonymous rule violates independence
in the 3-by-3 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 30th, 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 2nd, 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 16th, 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 |G||G|^|G| functions of n-variables from G to itself; so fnG <=  |G||G|^|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 log-exponential -- meaning that there exists a positive constant c such that fnG is eventually greater than 22^cn.  The Higman-Neumann result indicate that the asymptotic growth of (fnG) is an indicator of the properties of the group.

The following is a long-standing 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 2nd, 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 on-line 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 19th, 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.

 
University of Louisville, Department of Mathematics. Copyright © 2013.  All rights reserved. 
Comments to mailto:kezdy@louisville.edu.