Random bipartite posets and extremal problems (Q2220979): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3039124326 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 2003.07935 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2798999 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Standard examples as subposets of posets. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Forcing posets with large dimension to contain large standard examples / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partially Ordered Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The dimension of random ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4074927 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the independence number of random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the dimensions of ordered sets of bounded degree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5598296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4519896 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Better bounds for poset dimension and boxicity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3815303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5133646 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:37, 24 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random bipartite posets and extremal problems |
scientific article |
Statements
Random bipartite posets and extremal problems (English)
0 references
25 January 2021
0 references
The paper under review is a development on earlier work from \textit{P. Erdős} et al. [Random Struct. Algorithms 2, No. 3, 253--275 (1991; Zbl 0741.06001)] on random height 2 posets (i.e. where there are two sets of vertices of order \(n\) and each edge between the two sets is present with probability \(p\) independent of all other edges: we then say that each edge between two sets of vertices (lower and upper. Whereas, for good reason at that time, the earlier work focused on \(0\leq p\leq 1\), this paper concentrates on \(1/2\leq p\leq 1\), a region where the estimates in the earlier paper weakened as \(p\) approached 1. One of the key invariants considered is the dimension \(\dim(P)\) of the poset \(P\) (the smallest size of a set of total orders on the same ground set whose intersection is the partial order) which is somewhat analogous to the chromatic number of a graph, and the standard example number \(\operatorname{se}(P)\) of \(P\) (definition to follow) which is somewhat analogous to the clique number. \(\operatorname{se}(P)\) is defined to be 1 if \(P\) does not contain an poset isomorphic to any of the so-called standard examples and is the largest \(d\) such that \(P\) contains a subposet isomorphic to the standard example \(S_{d}\) otherwise. Here, \(S_{d}\) is the poset with \(d\) minimal elements \(\{a_{1},a_{2},\ldots, a_{d}\}\) and \(d\) maximal elements \(\{a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{d}^{\prime}\}\) and \(a_{i}\prec a_{j}^{\prime}\) for all \(j\neq i\), While in general it is known that one can have posets with \(\operatorname{se}(P)=1\) and \(\dim(P)\) arbitrarily large, it is of interest to investigate when there may be a link between them. The authors ask as Question 1 if there is a function \(\operatorname{sa}: \mathbb{N} \to \mathbb{N}\) such that if \(P\) is a poset on at most \(2n+1\)-vertices with \(\dim(P) \geq n-c\) then \(\operatorname{se}(P)\geq n-f(c)\). Their Question 2, generalising (e.g.) the fact that graphs on \(n\) vertices with no triangles have chromatic number at most \(C\sqrt{n/\log(n)}\) for some constant \(C\), is to ask what is the maximum dimension \(f(d,n)\) of an \(n\)-vertex poset \(P\) with \(\operatorname{se}(P)=d\). \par The main business of the paper is to sharpen somewhat technically both upper and lower bounds in the earlier paper for the dimension of the random bipartite posets above primarily for \(1/2\leq p\leq 1\), considering several different ranges of \(p\) separately. We omit the technical statement of these results but note their implication that the dimension does not behave monotonically as \(p\) approaches 1 and that the proofs involve much technical work with several concentration inequalities including those of Talagrand and Janson. \par Considering the implications for the two main questions for posets, on Question 1, it was already known [\textit{C. Biró} et al., Graphs Comb. 32, No. 3, 861--880 (2016; Zbl 1406.06001)] that \(\operatorname{sa}(c)=O(c^{2})\) and a lower bound was \(\tilde{\Omega}(c^{4/3})\) by a construction using finite projective planes. (The \(\tilde{\Omega}\) notation can hide logarithmic factors). The authors of the paper under review have talked in the past at conferences and seminars about how to improve this lower bound to \(\tilde{\Omega}(c^{3/2})\) using the asymmetric local lemma but now it is possible to write down a short self-contained proof of this. On Question 2, the value of \(f(2,n)\) has been well-understood for some time, it grows rather slowly, like \(\log_{2}\log_{2}(n)\) asymptotically (much more precise estimates are known). The paper under review shows that for \(d\geq 3\) there is a more substantial lower bound on \(f(d,n)\), namely \(\tilde{\Omega}(n^{\alpha_{d}})\) for a constant \(\alpha_{d}\) where we can take \(\alpha_{d}=1-\frac{2d-1}{d(d-1)}\). (For an upper bound it is known that \(f(d,n)=o(n)\)).
0 references
poset
0 references
bipartite poset
0 references
dimension
0 references
standard example
0 references
random bipartite graph dimension
0 references