On an equivalence in discrete extremal problems (Q1301649): Difference between revisions
From MaRDI portal
‎Created a new Item |
ReferenceBot (talk | contribs) ‎Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Sergei L. Bezrukov / rank | |||
Property / author | |||
Property / author: Sergei L. Bezrukov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge isoperimetric theorems for integer point arrays / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contributions to the geometry of Hamming spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4712283 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4250148 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4712355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge-isoperimetric inequalities in the grid / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A generalization of a combinatorial theorem of macaulay / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4338928 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Assignments of Numbers to Vertices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3964577 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4071752 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5870572 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Assignment of Numbers to Vertices / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 21:27, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On an equivalence in discrete extremal problems |
scientific article |
Statements
On an equivalence in discrete extremal problems (English)
0 references
13 March 2000
0 references
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.
0 references
extremal problems in graphs or posets
0 references
equivalence
0 references
chain
0 references