Random bipartite posets and extremal problems

DOI10.1007/S10474-020-01049-YMaRDI QIDQ2220979zbMATH OpenOpenAlexFDO

Publication date 25 January 2021

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07935

bipartite poset dimension poset random bipartite graph dimension standard example

Extremal problems in graph theory (05C35) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: Previously, ErdH{o}s, Kierstead and Trotter investigated the dimension of random height~

2

partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the F"{u}redi-Kahn upper bounds on dimension in terms of maximum degree; and (2)~developing machinery for estimating the expected dimension of a random labeled poset on

n

points. For these reasons, most of their effort was focused on the case

0 < p l e 1 / 2

. While bounds were given for the range

1 / 2 l e p < 1

, the relative accuracy of the results in the original paper deteriorated as

p

approaches~

1

. Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range

1 / 2 l e p < 1

. Our sharpened analysis shows that as

p

approaches~

1

, the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems.

Review text

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

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Random bipartite posets and extremal problems

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