skip to main content


Search for: All records

Creators/Authors contains: "Park, Jinyoung"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Proving the “expectation-threshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing propertyF\mathcal {F}on a finite setXX,\[pc(F)=O(q(F)log⁡<#comment/>ℓ<#comment/>(F)),p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})),\]wherepc(F)p_c(\mathcal {F})andq(F)q(\mathcal {F})are the threshold and “expectation threshold” ofF\mathcal {F}, andℓ<#comment/>(F)\ell (\mathcal {F})is the maximum of22and the maximum size of a minimal member ofF\mathcal {F}.

     
    more » « less
  2. Abstract

    We address a special case of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family of subsets of a finite setV. The full conjecture implies equivalence of the “Fractional Expectation‐Threshold Conjecture,” due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) “Expectation‐Threshold Conjecture” of the second author and G. Kalai. The conjecture under discussion here says there is a fixedLsuch that if, for a given , admits withand(a.k.a.  isweakly p‐small), then admits such a taking values in ( is‐small). Talagrand showed this when is supported on singletons and suggested, as a more challenging test case, proving it when is supported on pairs. The present work provides such a proof.

     
    more » « less
  3. null (Ed.)
  4. null (Ed.)
  5. null (Ed.)
  6. Abstract

    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