On an equivalence in discrete extremal problems (Q1301649): Difference between revisions

Let \(G=(V,E)\) be a finite graph. It has the nested solutions (NS) property (for \(F:2^V\to R)\) if there exists a total order on \(V\) such that for any \(t\in\{1,2, \dots, |V|\}\) the collection of the first \(t\) elements in this order is an \(F\)-optimal subset, i.e., a subset \(A\) of \(V\) such that \(F(A)\) is maximal (minimal if we wish) among all \(|A|\)-subsets of \(V\). Having the NS-property is a common occurrence in the (obtained) solutions to several classes of extremal problems in graphs or posets (via Hasse diagrams mostly) and using this observation as a base of operations the author is able to obtain results on Cartesian-product graphs \(G=G_ 1\times G_2\) in terms of results for the \(G_i\), \(i=1,2\). Thus, not only are classes of problems seen to be closely related (here: the edge isoperimetric problem; the shadow minimization problem; the maximum weight ideals in posets problem) but using a rather clever equivalence the author has produced he is e.g. able to handle the EIP-problem for \(G=T_1\times\cdots\times T_n\), the Cartesian product of finite trees, showing that it can be viewed as equivalent (in his sense) to \(Q=C_1\times\cdots\times C_n\), where \(C_i\) is the chain of order \(|T_i|\), i.e., a linear extension of \(T_i\). The key to the unscramble is the connection to posets and the MWI and the observation that in the NS-ness of the (extreme problems on) graphs Macauleyness of posets comes into play in a definitive and interesting way leading to ``solutions'' to these problems in several relevant cases.