Random bipartite posets and extremal problems (Q2220979): Difference between revisions

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)\)).