10 citations · 33 across the 23 of their papers we have counts for
4 papers · 1 filter
Down-set thresholds
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan
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 polynom…
Applications of Random Algebraic Constructions to Hardness of Approximation
Boris Bukh, Karthik C. S., Bhargav Narayanan
In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixe…
Friendly bisections of random graphs
Asaf Ferber, Matthew Kwan, Bhargav Narayanan +2
Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph admits a friendly bisection of its vertex set, i.e., a partition of its…
Sharp estimates for spanning trees
Steven Klee, Bhargav Narayanan, Lisa Sauermann
We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph on vertices has at most $(1/n^{2}) \prod_{v…