On the metric dimension of Cartesian products of a graph

With Nikita Polyanskii

A set of vertices resolves a graph if every vertex is uniquely determined by its vector of distances to the vertices in . 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 copies of the complete graph on vertices is .

Read on arXiv

On spectral radii of unraveled balls

If the average degree of after deleting any ball of radius is at least , then its second largest eigenvalue is at least .

Read on arXiv

Ramsey-nice families of graphs

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

A finite family of graphs is -nice if for every graph with (the chromatic number equals to the Ramsey number) and for every coloring of there exists a monochromatic copy of some . It seems conceivable that for any finite family of graphs that contains at least one forest, is -nice for all . We show that the conjecture holds for each of the three families consisting of two connected graphs with 3 edges each.

Read on arXiv

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

With Alexandr Polyanskii

We find the threshold such that, for every , the family of graphs of spectral radius has a finite forbidden subgraphs characterization. As a consequence, we establish the asymptotic formula of the maximum cardinality of equiangular lines with angle in for every .

Read on arXiv

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.

Read on arXiv

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

With Alexandr Polyanskii

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

Read on arXiv

Bipartite algebraic graphs without quadrilaterals

With Boris Bukh

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

Read on arXiv

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

With Boris Bukh

For each fixed , an -vertex graph not containing a cycle of length has at most edges.

Read on arXiv

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

Let be disjoint -point sets in . A colorful simplex is the convex hull of points each of which comes from a distinct . There always exists a point that is contained in at least colorful simplices.

Read on arXiv