2024/12/09 by Duan, Boyan, Ouyang, Minghui, Wang, Zheng
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.06402
We say that two partial orders on [n] are compatible if there exists a partial order that is finer than both of them. Under this compatibility relation, the set of all partial orders F and the set of all total orders G on [n] naturally define set families on each other, where each order is identified with the set of orders that are compatible with it. In this note, we determine the VC-dimension of F on G by showing that VCG(F) = \lfloor(n2)/(4)\rfloor for n ≥ 4. We also prove 2(n-3) ≤ VCF(G) ≤ n log2 n for n ≥ 1.