Ron Adin
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)