2019/09/20 by Jesse Geneson, Peter Tian, Peter M. Tian +4 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #cs.DM #graph theory and CDMA systems #math.CO #msc:05D99
paper · pdf · doi:10.48550/arxiv.1909.10330
arxiv created 2021/09/13 · arxiv updated 2021/09/15
Let up(r, t) = (a1 a2 … ar)t. We investigate the problem of determining the maximum possible integer n(r, t) for which there exist 2t-1 permutations π1, π2, …, π2t-1 of 1, 2, …, n(r, t) such that the concatenated sequence π1 π2 … π2t-1 has no subsequence isomorphic to up(r,t). This quantity has been used to obtain an upper bound on the maximum number of edges in k-quasiplanar graphs. It was proved by (Geneson, Prasad, and Tidor, Electronic Journal of Combinatorics, 2014) that n(r, t) ≤ (r-1)^22t-2. We prove that n(r,t) = Θ(r2t-1 \choose t), where the constant in the bound depends only on t. Using our upper bound in the case t = 2, we also sharpen an upper bound of (Klazar, Integers, 2002), who proved that Ex(up(r,2),n) < (2n+1)L where L = Ex(up(r,2),K-1)+1, K = (r-1)4 + 1, and Ex(u, n) denotes the extremal function for forbidden generalized Davenport-Schinzel sequences. We prove that K = (r-1)4 + 1 in Klazar's bound can be replaced with K = (r-1) \binomr2+1. We also prove a conjecture from (Geneson, Prasad, and Tidor, Electronic Journal of Combinatorics, 2014) by showing for t ≥ 1 that Ex(a b c (a c b)t a b c, n) = n 2^(1)/(t!)α(n)t ± O(α(n)t-1). In addition, we prove that Ex(a b c a c b (a b c)t a c b, n) = n 2^(1)/((t+1)!)α(n)t+1 ± O(α(n)t) for all t ≥ 1.