The discrete analog of classic isoperimetry problem (DIP) appears in applications such as chip design, Pattern Recognition, design of ad-hock networks and others. DIP is a well-known combinatorial optimization problem with many consequences. Applied problems such as cross intersection networks, routing, WSN protocols, best match search, are solved using DIP. The later was an open problem by R. Rivest for 40 years. Almost complete description of the set of DIP sets and their asymptotics are given in terms of n-cube geometry and Poisson type distributions.
The discrete analog of classic isoperimetry problem (DIP)