10 citations · 33 across the 23 of their papers we have counts for
45 papers
Thresholds for geometric graphs
Bhargav Narayanan
A metric probability space admits thresholds if the random geometric graph on has a threshold for every monotone graph property. We connect the existence of thresholds to t…
How to pick your football team
Bhargav Narayanan
Team captains Alice and Bob divide up footballers, each reduced to a real-valued score, into two teams of footballers each. On each turn, one captain plays picker, and the…
Antichain Codes
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan +1
A family of sets is said to be an antichain if for all distinct , and it is said to be a distance- code if every pair of distinct elements of …
A Counterexample to a Directed KKL Inequality
Quentin Dubroff, Shivam Nadimpalli, Bhargav Narayanan
We show that the natural directed analogues of the KKL theorem [KKL88] and the Eldan--Gross inequality [EG20] from the analysis of Boolean functions fail to hold. This is in contra…
Reconstructing random pictures
Bhargav Narayanan, Corrine Yap
Given a random binary picture of size , i.e., an grid filled with zeros and ones uniformly at random, when is it possible to reconstruct from its -dec…
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…
Simplicial homeomorphs and trace-bounded hypergraphs
Jason Long, Bhargav Narayanan, Corrine Yap
Our first main result is a uniform bound, in every dimension , on the topological Turán numbers of -dimensional simplicial complexes: for each …
The threshold for the square of a Hamilton cycle
Jeff Kahn, Bhargav Narayanan, Jinyoung Park
Resolving a conjecture of Kühn and Osthus from 2012, we show that is the threshold for the random graph to contain the square of a Hamilton cycle.
A universal exponent for homeomorphs
Peter Keevash, Jason Long, Bhargav Narayanan +1
We prove a uniform bound on the topological Turán number of an arbitrary two-dimensional simplicial complex : any -vertex two-dimensional complex with at least $C_S n^{3-1/5}…
Subgraphs of large connectivity and chromatic number
António Girão, Bhargav Narayanan
Resolving a problem raised by Norin, we show that for each , there exists an such that every graph with chromatic number at least conta…
Counting independent sets in regular hypergraphs
Jozsef Balogh, Bela Bollobas, Bhargav Narayanan
Amongst -regular -uniform hypergraphs on vertices, which ones have the largest number of independent sets? While the analogous problem for graphs (originally raised by Gr…
Thresholds versus fractional expectation-thresholds
Keith Frankston, Jeff Kahn, Bhargav Narayanan +1
Proving a conjecture of Talagrand, a fractional version of the 'expectation-threshold' conjecture of Kalai and the second author, we show for any increasing family on a finite…
Disproportionate division
Logan Crew, Bhargav Narayanan, Sophie Spirkl
We study the disproportionate version of the classical cake-cutting problem: how efficiently can we divide a cake, here , among agents with different demands $α_1, α_2,…
Slowdown for the geodesic-biased random walk
Mikhail Beliayeu, Petr Chmel, Bhargav Narayanan +1
Given a connected graph with some subset of its vertices excited and a fixed target vertex, in the geodesic-biased random walk on , a random walker moves as follows: from an…
On symmetric intersecting families of vectors
Sean Eberhard, Jeff Kahn, Bhargav Narayanan +1
A family of vectors is said to be intersecting if any two elements of agree on at least one coordinate. We prove, for fixed , that the size of a symm…
Turán theorems for unavoidable patterns
António Girão, Bhargav Narayanan
We prove Turán-type theorems for two related Ramsey problems raised by Bollobás and by Fox and Sudakov. First, for , we show that any two-colouring of the complete graph o…
Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
Bhargav Narayanan, Mathias Schacht
For positive integers , an -uniform hypergraph is called an -cycle if there exists a cyclic ordering of its vertices such that each of its edges consists of …
Product-free sets in the free semigroup
Imre Leader, Shoham Letzter, Bhargav Narayanan +1
In this paper, we study product-free subsets of the free semigroup over a finite alphabet . We prove that the maximum density of a product-free subset of the free semigroup over…
Spanning surfaces in 3-graphs
Agelos Georgakopoulos, John Haslegrave, Richard Montgomery +1
We prove a topological extension of Dirac's theorem suggested by Gowers in 2005: for any connected, closed surface , we show that any two-dimensional simplicial comple…
Exceptional graphs for the random walk
Juhan Aru, Carla Groenland, Tom Johnston +3
If is the simple random walk on the square lattice , then induces a random walk on any spanning subgraph $G\subset \mathbb…
On regular 3-wise intersecting families
Keith Frankston, Jeff Kahn, Bhargav Narayanan
Ellis and the third author showed, verifying a conjecture of Frankl, that any -wise intersecting family of subsets of admitting a transitive automorphism group…