Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Logic and Semantics Seminar
4th February 2005: Max Kanovich
Computer Laboratory > Research > TSG > Logic and Semantics Seminar > 4th February 2005: Max Kanovich

Speaker: Max Kanovich, Queen Mary, University of London
Title: Resolving Problems in the World of Integer Partitions by Techniques from the Rewriting World
Time: 4th February 2005, 14:00
Venue: William Gates Building, room FW11
Abstract:

One basic activity in combinatorics is to establish combinatorial identities by so-called `bijective proofs,' which consists in constructing explicit bijections between two types of the combinatorial objects under consideration.

We show how such bijective proofs can be extracted in a systematic way from the `lattice properties' of partition ideals, and how the desired bijections are computed by means of multiset rewriting, for a variety of combinatorial problems involving partitions. Establishing the required bijections involves a two-directional reduction technique novel in the sense that forward and backward applications of rewrite rules head, respectively, for two different normal forms (representing the two combinatorial types).

The basic methodological idea is to study the filters, the complement of the partition ideals, and more specifically, the sets of all minimal elements of these filters (`supports').

Based on the two-way rewriting technique, we fully characterize all equinumerous partition ideals when each of these supports is made of pairwise disjoint multisets.

As a corollary, a first `bijective' (and transparent) proof is given for all equinumerous classes of the partition ideals of order 1 from the classical book `The Theory of Partitions' by G. Andrews.

Furthermore, our criterion provides the bijection that preserves more structure (a `statistics' expressing how much a partition is far from being in the ideal).

It is well-known that non-overlapping multiset rules are confluent. As for termination, it generally fails even for multiset rewriting systems that satisfy certain natural invariant balance conditions. The main technical development here (which is important for establishing that the mapping yielding the combinatorial bijection is functional) is that the restricted two-directional strong normalization holds for the multiset rewriting systems in question.

Lastly, we address the case of filters having overlapping supports. We show how two-directional multiset rewriting techniques can be used to construct `bijective proofs' for a new series of partition identities related to Fibonacci and Lucas numbers.

No acquaintance with logic or math is required.