Finite Combinatorics Papers

Andreas Blass

The papers on this page are listed in reverse chronological order. My joint papers with Bruce Sagan are also available from his web site. Papers about infinitary combinatorics are on the set theory page.


Random orders and gambler's ruin, joint with Gabor Braun (Electronic J. Comb. 12 (2005) R12)

PDF

We prove a conjecture of Droste and Kuske about the probability that 1 is minimal in a certain random linear ordering of the set of natural numbers. We also prove generalizations, in two directions, of this conjecture: when we use a biased coin in the random process and when we begin the random process with a specified ordering of a finite initial segment of the natural numbers. Our proofs use a connection between the conjecture and a question about the game of gambler's ruin. We exhibit several different approaches (combinatorial, probabilistic, generating function) to the problem, of course ultimately producing equivalent results.


Explicit Graphs with Extension Properties, joint with Benjamin Rossman (Bull. Europ. Assoc. Theoret. Comp. Sci. 86 (2005) 166--175)

PDF

We exhibit explicit, combinatorially defined graphs satisfying the k-th extension axiom: Given any set of k distinct vertices and any partition of it into two pieces, there exists another vertex adjacent to all of the vertices in the first piece and to none in the second.


Homotopy and Homology of Finite Lattices (Electronic J. Comb. 10(1) (2003) Research Paper R30)

PostScript or PDF

We exhibit an explicit homotopy equivalence between the geometric realizations of the order complex of a finite lattice and the simplicial complex of coreless sets of atoms whose join is not the top element 1. This result, which extends a theorem of Segev, leads to a description of the homology of a finite lattice, extending a result of Bjoerner for geometric lattices.


Characteristic and Ehrhart Polynomials, joint with Bruce Sagan, (J. Alg. Comb. 7 (1998) 115-126)

PostScript or PDF

Let A be a subspace arrangement and let chi(A,t) be the characteristic polynomial of its intersection lattice L(A). We show that if the subspaces in A are taken from L(B_n), where B_n is the type B Weyl arrangement, then chi(A,t) counts a certain set of lattice points. This is the only known combinatorial interpretation of this polynomial in the subspace case. One can use this result to study the partial factorization of chi(A,t) over the integers and the coefficients of its expansion in various bases for the polynomial ring R[t]. Next we prove that the characteristic polynomial of any Weyl hyperplane arrangement can be expressed in terms of an Ehrhart quasi-polynomial for its affine Weyl chamber. Note that our first result deals with all subspace arrangements embedded in B_n while the second deals with all finite Weyl groups but only their hyperplane arrangements.


Moebius Functions of Lattices, joint with Bruce Sagan, (Adv. Math. 127 (1997) 94-123)

PostScript or PDF

We introduce the concept of a bounded below set in a lattice. This can be used to give a generalization of Rota's broken circuit theorem to any finite lattice. We then show how this result can be used to compute and combinatorially explain the Moebius function in various examples including non-crossing set partitions, shuffle posets, and integer partitions in dominance order. Next we present a generalization of Stanley's theorem that the characteristic polynomial of a semimodular supersolvable lattice factors over the integers. We also give some applications of this second main theorem, including the Tamari lattices.


Seven trees in one (J. Pure Appl. Alg. 103 (1995) 1-21)

PostScript or PDF

Following a remark of Lawvere, we explicitly exhibit a particularly elementary bijection between the set T of finite binary trees and the set T^7 of seven-tuples of such trees. "Particularly elementary" means that the application of the bijection to a seven-tuple of trees involves case distinctions only down to a fixed depth (namely four) in the given seven-tuple. We clarify how this and similar bijections are related to the free commutative semiring on one generator X subject to X=1+X^2. Finally, our main theorem is that the existence of particularly elementary bijections can be deduced from the provable existence, in intuitionistic type theory, of any bijections at all.


Quasi-Varieties, Congruences, and Generalized Dowling Lattices (J. Alg. Comb. 4 (1995) 277-294)
and
correction (ibid. 5 (1996) 167)

PostScript of the paper and the correction or PDF of the paper and the correction

Dowling lattices and their generalizations introduced by Hanlon are interpreted as lattices of congruences associated to certain quasi-varieties of sets with group actions. This interpretation leads, by a simple application of Moebius inversion, to polynomial identities which specialize to Hanlon's evaluation of the characteristic polynomials of generalized Dowling lattices. Analogous results are obtained for a few other quasi-varieties.


Ultrafilters: Where Topological Dynamics = Algebra = Combinatorics (Topology Proc. 18 (1993) 33-56)

PostScript or PDF

We survey some connections between topological dynamics, semigroups of ultrafilters, and combinatorics. As an application, we give a proof, based on ideas of Bergelson and Hindman, of the Hales-Jewett partition theorem.