Combinatorics Seminar
When: Sunday, April 6, 10am
Where: Schreiber 309
Speaker: Moshe Schwartz, Ben Gurion University,
Title: Exact Capacity of some Two-Dimensional Constrained Systems
Abstract:
A two-dimensional constrained system is the set of all
two-dimensional binary arrays which obey a certain constraint.
A well-known example of such constraints is the (0,1)-RLL constraint,
i.e., no two adjacent zeros (horizontally or vertically) in the array.
This is equivalent to counting the number of independent sets in the
grid graph. When the diagonal directions are also included this is
equivalent to counting arrays of non-attacking kings. The logarithm
of the number of such arrays, divided by the area of the array
as its sides go to infinity, was defined by Shannon as the capacity
of the constraint.
We address the well-known problem of determining the capacity of
two-dimensional constrained systems. While the one-dimensional
case is well understood to the extent that there are techniques
for rigorously deriving the exact capacity, in contrast, computing
the exact capacity of a two-dimensional constrained system is still
an elusive research challenge. The only known non-trivial exception
in the two-dimensional case is an exact (however, not rigorous)
solution to the (0,1)-RLL system on the hexagonal lattice (the hard
hexagon entropy constant). Furthermore, only exponential-time
algorithms are known for the related problem of counting the exact
number of constrained two-dimensional information arrays.
We present the first known rigorous technique that yields an exact
capacity of a two-dimensional constrained coding system. In
addition, we devise an efficient (polynomial time) algorithm for
counting the exact number of constrained arrays of any given size.
Our approach is a composition of a number of ideas and techniques:
describing the capacity problem as a solution to a counting
problem in networks of relations, graph-theoretic tools originally
developed in the field of statistical mechanics, techniques for
efficiently simulating quantum circuits, as well as ideas from the
theory related to the spectral distribution of Toeplitz matrices.
Using our technique we derive a closed form solution to the
capacity related to the Path-Cover constraint in a two-dimensional
triangular array (assigning 1's and 0's to the edges of the
triangular grid such that every vertex is incident to either one
or two 1's). The resulting calculated capacity is 0.72399217...
Path-Cover is a generalization of the well known one-dimensional
(0,1)-RLL constraint for which the capacity is known to be
0.69424... (which is the base 2 logarithm of the golden ratio).
The talk is self-contained, and is based on a joint work with
Jehoshua Bruck from Caltech.