More Like this

1. Down‐set thresholds

   https://doi.org/10.1002/rsa.21148  

   Gunby, Benjamin ; He, Xiaoyu ; Narayanan, Bhargav ( April 2023 , Random Structures & Algorithms)

   We elucidate the relationship between the threshold and the expectation‐threshold of a down‐set. Qualitatively, our main result demonstrates that there exist down‐sets with polynomial gaps between their thresholds and expectation‐thresholds; in particular, the logarithmic gap predictions of Kahn–Kalai and Talagrand (recently proved by Park–Pham and Frankston–Kahn–Narayanan–Park) about up‐sets do not apply to down‐sets. Quantitatively, we show that any collection of graphs on that covers the family of all triangle‐free graphs on satisfies the inequality for some universal , and this is essentially best‐possible.

    

   more » « less
2. Vector balancing in Lebesgue spaces

   https://doi.org/10.1002/rsa.21113  

   Reis, Victor ; Rothvoss, Thomas ( August 2022 , Random Structures & Algorithms)

   TheKomlósconjecture suggests that for any vectors there exist so that . It is a natural extension to ask what ‐norm bound to expect for . We prove a tight partial coloring result for such vectors, implying a nearly tight full coloring bound. As a corollary, this implies a special case of Beck–Fiala's conjecture. We achieve this by showing that, for any , a symmetric convex body with Gaussian measure at least admits a partial coloring. Previously this was known only for asmallenough . Additionally, we show that a hereditary volume bound suffices to provide such Gaussian measure lower bounds.

    

   more » « less
3. On the upper tail problem for random hypergraphs

   https://doi.org/10.1002/rsa.20975  

   Liu, Yang P. ; Zhao, Yufei ( November 2020 , Random Structures & Algorithms)

   The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.

    

   more » « less
4. Tuza's conjecture for random graphs

   https://doi.org/10.1002/rsa.21057  

   Kahn, Jeff ; Park, Jinyoung ( November 2021 , Random Structures & Algorithms)

   A celebrated conjecture of Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge‐disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely:urn:x-wiley:rsa:media:rsa21057:rsa21057-math-0001

    

   more » « less
5. On the number of high‐dimensional partitions

   https://doi.org/10.1112/plms.12586  

   Pohoata, Cosmin ; Zakharov, Dmitrii ( February 2024 , Proceedings of the London Mathematical Society)

   Let denote the number of ‐dimensional partitions with entries from . Building upon the works of Balogh–Treglown–Wagner and Noel–Scott–Sudakov, we show that when ,holds for all . This makes progress toward a conjecture of Moshkovitz–Shapira [Adv. in Math. 262 (2014), 1107–1129]. Via the main result of Moshkovitz and Shapira, our estimate also determines asymptotically a Ramsey‐theoretic parameter related to Erdős–Szekeres‐type functions, thus solving a problem of Fox, Pach, Sudakov, and Suk [Proc. Lond. Math. Soc. 105 (2012), 953–982]. Our main result is a new supersaturation theorem for antichains in , which may be of independent interest.

    

   more » « less