# On the metric dimension of Cartesian products of a graph

## With Nikita Polyanskii

A set of vertices $S$ resolves a graph if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of a graph is the minimum cardinality of a resolving set of the graph. We prove that the metric dimension of the Cartesian product of $n$ copies of the complete graph on $q$ vertices is $(2+o(1))n/\log_q n$.

# On spectral radii of unraveled balls

If the average degree of $G$ after deleting any ball of radius $r$ is at least $d$, then its second largest eigenvalue is at least $2\sqrt{d-1}\cos\left(\frac{\pi}{r+1}\right)$.

# Ramsey-nice families of graphs

## With Ron Aharoni, Noga Alon, Michal Amir, Penny Haxell, Dan Hefetz, Gal Kronenberg and Alon Naor

A finite family $\mathcal{F}$ of graphs is $k$-nice if for every graph $G$ with $\chi(G) = R_k(\mathcal{F})$ (the chromatic number equals to the Ramsey number) and for every coloring of $E(G)$ there exists a monochromatic copy of some $F\in\mathcal{F}$. It seems conceivable that for any finite family of graphs $\mathcal{F}$ that contains at least one forest, $\mathcal{F}$ is $k$-nice for all $k \ge k_0(\mathcal{F})$. We show that the conjecture holds for each of the three families consisting of two connected graphs with 3 edges each.

# Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines

## With Alexandr Polyanskii

We find the threshold $\lambda^* = \sqrt{2+\sqrt{5}}$ such that, for every $% $, the family of graphs of spectral radius $\le \lambda$ has a finite forbidden subgraphs characterization. As a consequence, we establish the asymptotic formula of the maximum cardinality of equiangular lines with angle $\arccos\alpha$ in $\mathbb{R}^n$ for every $\alpha > \frac{1}{1+2\lambda^*}$.

# Finding a best approximation pair of points for two polyhedra

## With Ron Aharoni and Yair Censor

Given two disjoint convex polyhedra, we propose a process, based on projections onto the half-spaces defining the two polyhedra, for finding a pair of points, one in each polyhedron, attaining the minimum distance.

# Proof of László Fejes Tóth's zone conjecture

## With Alexandr Polyanskii

A zone of width $\omega$ on the unit sphere is the set of points within spherical distance $\omega/2$ of a given great circle. We show that the total width of any collection of zones covering the unit sphere is at least $\pi$.

# Bipartite algebraic graphs without quadrilaterals

## With Boris Bukh

We conjecture that every algebraic hypersurface that gives rise to a $K_{s,t}$-free graph is equivalent, in a suitable sense, to a low-degree hypersurface. We establish a version of this conjecture for $K_{2,2}$-free graphs.

# A bound on the number of edges in graphs without an even cycle

## With Boris Bukh

For each fixed $k$, an $n$-vertex graph not containing a cycle of length $2k$ has at most $80\sqrt{k}\log k \cdot n^{1+1/k}+O(n)$ edges.

# A slight improvement to the colored Bárány’s theorem

Let $P_0, \dots, P_d$ be $d + 1$ disjoint $n$-point sets in $\mathbb{R}^d$. A colorful simplex is the convex hull of $d + 1$ points each of which comes from a distinct $P_i$. There always exists a point that is contained in at least $\frac{2d}{(d+1)(d+1)!}n^d$ colorful simplices.