Search

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]