Zobrazeno 1 - 10
of 156
pro vyhledávání: '"NARAYANAN, BHARGAV"'
Let $\epsilon_{1},\ldots,\epsilon_{n}$ be a sequence of independent Rademacher random variables. We prove that there is a constant $c>0$ such that for any unit vectors $v_1,\ldots,v_n\in \mathbb{R}^2$, $$\Pr\left[||\epsilon_1 v_1+\ldots+\epsilon_n v_
Externí odkaz:
http://arxiv.org/abs/2408.11034
We study several basic problems about colouring the $p$-random subgraph $G_p$ of an arbitrary graph $G$, focusing primarily on the chromatic number and colouring number of $G_p$. In particular, we show that there exist infinitely many $k$-regular gra
Externí odkaz:
http://arxiv.org/abs/2312.08340
We study how many copies of a graph $F$ that another graph $G$ with a given number of cliques is guaranteed to have. For example, one of our main results states that for all $t\ge 2$, if $G$ is an $n$ vertex graph with $kn^{3/2}$ triangles and $k$ is
Externí odkaz:
http://arxiv.org/abs/2312.08265
A family of sets $A$ is said to be an antichain if $x\not\subset y$ for all distinct $x,y\in A$, and it is said to be a distance-$r$ code if every pair of distinct elements of $A$ has Hamming distance at least $r$. Here, we prove that if $A\subset 2^
Externí odkaz:
http://arxiv.org/abs/2212.08406
Autor:
Narayanan, Bhargav, Yap, Corrine
Given a random binary picture $P_n$ of size $n$, i.e., an $n\times n$ grid filled with zeros and ones uniformly at random, when is it possible to reconstruct $P_n$ from its $k$-deck, i.e., the multiset of all its $k\times k$ subgrids? We demonstrate
Externí odkaz:
http://arxiv.org/abs/2210.09410
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 contrast to several other isoperimetric inequalities on the Boolean hypercub
Externí odkaz:
http://arxiv.org/abs/2210.02035
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 parti
Externí odkaz:
http://arxiv.org/abs/2112.08525
In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural. (*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced b
Externí odkaz:
http://arxiv.org/abs/2111.05518
Resolving a conjecture of F\"uredi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in whic
Externí odkaz:
http://arxiv.org/abs/2105.13337
We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph $G$ on $n$ vertices has at most $(1/n^{2}) \prod_{v \in V(G)} (d(v)+1)$ spanning trees. This result is tight (for complet
Externí odkaz:
http://arxiv.org/abs/2102.01669