Algebra, Combinatorics, and Number Theory Seminar
 Wednesday, October 27th, 2015 at 3:00pm NS 212DCharacterization 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 two-colored graph. These "pressing actions", which alter the colors and adjacencies in the graph, bear a certain resemblance to the classic "lights-out" 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.

Past Seminars...
 Wednesday, October 20th, 2015 at 3:00pm NS 212DRyann Cartor, Ryan Gipson, Jeremy Vates University of Louisville Abstract:  Multivariate Public Key Cryptography (MPKC) is one of the most attractive post-quantum 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 field-based 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 7th, 2015 at 3:00pm NS 212DSome 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 off-diagonal 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 30th, 2015 at 3:00pm NS 212DSome 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 off-diagonal 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 S-number.

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

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

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

 Wednesday, December 3rd, 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 end-vertex. 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 end-vertex 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 19th, 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 8th, 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 1st, 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 10th, 2014 at 1:00pm NS 212F Professor Jinjia Li University of Louisville Abstract: Given a bounded-above free complex over a Cohen-Macaulay ring such that the homology are of finite length, we describe a construction which connects its homology to that of another complex with fewer non-vanishing 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 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.

 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 Biró 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.