2017/10/13 by Ryan R. Martin, Abhishek Methuku, Martin, Ryan R. +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1710.05057
openalex publication_date 2017/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The poset Yk+1, 2 consists of k+2 distinct elements x1, x2, …, xk, y1,y2, such that x1 ≤ x2 ≤ … ≤ xk ≤ y1,~y2. The poset Y'k+1, 2 is the dual of Yk+1, 2 Let \rmLa\sharp(n,\Yk+1, 2, Y'k+1, 2\) be the size of the largest family F ⊂ 2[n] that contains neither Yk+1,2 nor Y'k+1,2 as an induced subposet. Methuku and Tompkins proved that \rmLa\sharp(n, \Y3,2, Y'3,2\) = Σ(n,2) for n ≥ 3 and they conjectured the generalization that if k ≥ 2 is an integer and n ≥ k+1, then \rmLa\sharp(n, \Yk+1,2, Y'k+1,2\) = Σ(n,k). In this paper, we introduce a simple discharging approach and prove this conjecture.