On an equivalence in discrete extremal problems

DOI10.1016/S0012-365X(99)00013-8MaRDI QIDQ1301649zbMATH OpenFDO

Authors Sergej L. Bezrukov

Publication date 13 March 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00013-8

zbMATH Keywords

chain equivalence extremal problems in graphs or posets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07)

Review text

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: On an equivalence in discrete extremal problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301649)