Zobrazeno 1 - 10
of 1 247
pro vyhledávání: '"Wigderson, A."'
The canonical Ramsey theorem of Erd\H{o}s and Rado implies that for any graph $H$, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph $K_N$ contains a monochromatic, lexicographic, or rainbow copy of $H$. Th
Externí odkaz:
http://arxiv.org/abs/2410.08644
Autor:
Wigderson, Yuval
A graph $G$ is said to be Ramsey size-linear if $r(G,H) =O_G (e(H))$ for every graph $H$ with no isolated vertices. Erd\H{o}s, Faudree, Rousseau, and Schelp observed that $K_4$ is not Ramsey size-linear, but each of its proper subgraphs is, and they
Externí odkaz:
http://arxiv.org/abs/2409.05931
A highly influential result of Nikiforov states that if an $n$-vertex graph $G$ contains at least $\gamma n^h$ copies of a fixed $h$-vertex graph $H$, then $G$ contains a blowup of $H$ of order $\Omega_{\gamma,H}(\log n)$. While the dependence on $n$
Externí odkaz:
http://arxiv.org/abs/2408.12913
A graph $G$ is said to be $p$-locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$. A famous conjecture of Kohayakawa, Nagle, R\"odl, and Schacht predicts that locally dense graphs have, asymptotica
Externí odkaz:
http://arxiv.org/abs/2406.12418
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous questions and structures in physics, mathematics, computer science, optim
Externí odkaz:
http://arxiv.org/abs/2405.15368
Autor:
Morawski, Patryk, Wigderson, Yuval
We show that any graded digraph $D$ on $n$ vertices with maximum degree $\Delta$ has an oriented Ramsey number of at most $C^\Delta n$ for some absolute constant $C > 1$, improving upon a recent result of Fox, He, and Wigderson. In particular, this i
Externí odkaz:
http://arxiv.org/abs/2405.01069
Autor:
Andrews, Robert, Wigderson, Avi
We design polynomial size, constant depth (namely, $\mathsf{AC}^0$) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, B\'ezout coefficients, squarefree decomp
Externí odkaz:
http://arxiv.org/abs/2404.10839
For a field $\mathbb{F}$ and integers $d$ and $k$, a set ${\cal A} \subseteq \mathbb{F}^d$ is called $k$-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ vectors of ${\cal A}$ include an orthogonal pair. We prove that for ever
Externí odkaz:
http://arxiv.org/abs/2404.01057
A graph $G$ is said to be Ramsey for a tuple of graphs $(H_1,\dots,H_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the
Externí odkaz:
http://arxiv.org/abs/2402.03045
Autor:
Kwan, Matthew, Wigderson, Yuval
The inertia bound and ratio bound (also known as the Cvetkovi\'c bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number $\alpha(G)$ of a graph $G$ in terms of spectral inform
Externí odkaz:
http://arxiv.org/abs/2312.04925