Isoperimetric Tools

Solution of the MRI for the Cartesian product of two posets

This tool is intended for solving the Maximum Weight Ideal problem (MWI) on the cartesian product of two ranked posets. See here for the problem statement. The cartesian product P x Q of posets (P, <_P) and (Q, <_Q) is defined as follows. The element set of P x Q is the cartesian product of the element sets of P and Q, and for elements (p₁, q₁) and (p₂, q₂) we write (p₁, q₁) <_PxQ (p₂, q₂) iff p₁ <_P p₂ and q₁ <_P q₂.

A particular version of MWI is the Maximum Rank Ideal (MRI) problem, where the posets are assumed ranked and the weight function equals the rank function. It is easily seen that the product of two ranked posets is a ranked poset too and for the rank function on P x Q one has r_PxQ(p, q) = r_P(p) + r_Q(q).

It is assumed here that the posets P and Q admit nested solutions in MRI, and a solution of the MRI problem is known for each of them. That is, one should know the values w_P(k) and w_Q(m) for each k = 1 . . |P| and m = 1 . . |Q|. To apply this tool one should enter the increments of the MWI function for P and Q, that is, the numbers delta_P(k) = w_P(k) - w_P(k-1) for k = 1 . . |P| and delta_Q(m) = w_Q(m) - w_Q(m-1) for m = 1 . . |Q|. By definition, delta_P(1) = delta_Q(1) = 0. In case of MRI the increments must satisfy the necessary condition delta(m) <= delta(m-1) + 1.

The default values of the delta-sequences in the input fields below correspond to the Petersen poset [2]. Thus, this tool provides a numeric solution to the edge-isoperimetric problem on the Cartesian product of two Petersen graphs, which is mentioned in [2] without a proof.

Clicking on the button causes sending your delta-sequences for processing. The processing consists of generating all ideals of the |P| x |Q| grid and computing their ranks. The program is based on the algorithm from [1]. Since the number of ideals equals the order of the poset L(|P|, |Q|), which is the binomial coefficient C(|P|+|Q|, |P|), the computations might take some time. The current process status is indicated by the progress bar.

After computing the maximum weights of ideals of P x Q for each value of the cardinality, the program checks the existence of nested solutions (NSS). If nested solutions do exist, the system displays one of the total orders. Otherwise, one of the longest initial nested series will be shown.

References

[1] X. Berenguer, L.H. Harper: Estabilizacion y resolucion de algunos problemas combinatorios en grafos simetricos, Questio, vol. 3 (1979), No. 2, 105-117.

[2] S.L. Bezrukov, S. Das, R. Elsässer: An edge isoperimetric problem for powers of the Petersen graph, Annals of Combinatorics, vol. 4 (2000), 153-169.