15 papers
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…
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…