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

From MaRDI portal
Importer (talk | contribs)
‎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
Normal 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 / namelinks / 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
    0 references

    Identifiers