Workshop on Combinatorics

Combined testimonies: Mathematical aspects of a Talmudic problem
Charging the minimum of two testimonies on a monetary commitment is a basic Talmudic principle. This rule has been generalized to $n$ testimonies, with fascinating algorithms by Nachmanides and others, and appears in the classical Shulchan-'Arukh codex of Jewish law. However, no careful mathematical analysis of it seems to have appeared in the literature.

Algebraic, geometric and probabilistic aspects of this problem will be discussed. Special attention will be given to Nachmanides' algorithm. It will be shown that one of its ancient variants is essentially equivalent to the Karmarkar-Karp differencing method for the (NP-complete) partition problem.

This is joint work with Yuval Roichman.

Toufik Mansour

Smooth partitions and Chebyshev polynomials
A \emph{partition} of the set $[n]=\{1,2,\ldots,n\}$ is a collection $\{B_1,\ldots ,B_k\}$ of nonempty disjoint subsets of $[n]$ (called \emph{blocks}) whose union equals $[n]$. A partition of $[n]$ is said to be {\em smooth} if $i\in B_s$ implies that $i+1\in B_{s-1}\cup B_s\cup B_{s+1}$ for all $i\in[n-1]$ ($B_0=B_{k+1}=\emptyset$). This paper presents the generating function for the number of $k$-block, smooth partitions of $[n]$, written in terms of Chebyshev polynomials of the second kind. There follows a formula for the number of $k$-block, smooth partitions of $[n]$ written in terms of trigonometric sums. Also, by first establishing a bijection between the set of smooth partitions of $[n]$ and a class of symmetric Dyck paths of semilength $2n-1$, we prove that the counting sequence for smooth partitions of $[n]$ is Sloane's A005773.

Roy Meshulam

Fourier matrix, uncertainty and hypertrees
A remarkable theorem of Chebotarev (1925) asserts that if n is prime, then any square submatrix of the Fourier matrix of order n is nonsingular. We shall discuss two applications of Chebotarev's theorem. The first concerns an improvement of the discrete uncertainty principle for finite abelian groups. The second application (joint work with N. Linial and M. Rosenthal) concerns the topology of certain arithmetically constructed spaces called Sum Complexes. In particular, it is shown that sum complexes on a prime number of vertices are hypertrees, i.e. have vanishing rational homology.

Yuval Roichman

Flips, arrangemts and tableaux
Flips of diagonals in colored triangle-free triangulations of a convex polygon are interpreted as moves between two adjacent chambers in a certain graphic hyperplane arrangement. Properties of geodesics in the associated flip graph are deduced. In particular, it is shown that every diagonal is flipped exactly once in a geodesic between distinguished pairs of antipodes, proving a conjecture of Richard Stanley. Furthermore, the set of these geodesics is described via a bijection to Young tableaux of a truncated shifted staircase shape. (joint with Ron Adin)