Algebraic and Combinatorial Coding Theory
Combinatorial Coding Theory I

The Capacity of Multidimensional Permutations with Restricted Movement

Dor Elimelech

Date & Time

01:00 am – 01:00 am


We study the multidimensional constrained systems of $\Z^d$-permutations with restricted movement. We show a correspondence between these restricted permutations and perfect matchings. We use the theory of perfect matchings to investigate several two-dimensional cases, for which we compute the exact capacity of the constrained system, and prove the existence of a polynomial-time algorithm for counting admissible patterns. We prove that the capacity of $\Z^d$-permutations restricted by a set with full affine dimension depends only on the size of the set. We use this result in order to compute the exact capacity for a class of two-dimensional constrained systems.


Dor Elimelech

Ben-Gurion University of the Negev

Session Chair

Navin Kashyap

Indian Institute of Science