An isoperimetric inequality for Hamming balls and local expansion in hypercubes (with Amir Yehudayoff)

Denote by the -dimensional Hamming ball of radius . If and the size of a subset of satisfies , then the vertex boundary of is at least .

Cooperative colorings of trees and bipartite graphs (with Ron Aharoni, Eli Berger, Maria Chudnovsky and Frédéric Havet)

Given a system of graphs on the same vertex set , a cooperative coloring for is a choice of vertex sets , such that is independent in and . We give bounds on the minimal such that every graphs with maximum degree have a cooperative coloring, in the cases that (a) the graphs are trees, (b) the graphs are all bipartite.

Rainbow fractional matchings (with Ron Aharoni and Ron Holzman)

Any family of sets of edges in an -uniform hypergraph, each having a fractional matchings number of size , has a rainbow matching of size (that is, a set of edges from distinct ’s which supports such a fractional matching).

Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines (with Alexandr Polyanskii)

We show that the family of graphs of spectral radius has a finite forbidden subgraphs characterization if and only if and , where and is the largest root of . As a consequence, we establish the asymptotic formula of the maximum cardinality of equiangular lines with angle in for every .


On capacities of the two-user union channel with complete feedback (with Nikita Polyanskii and Ilya Vorobyev)

We complete the line of research on the optimal symmetric rate point in the channel capacity region of the two-user union channel, and we construct a practical near-optimal zero-error communication scheme.

IEEE Transactions on Information Theory (2019) 65: 2774-2781 article

On the metric dimension of Cartesian powers 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 .

Journal of Combinatorial Theory, Series A (2019) 165: 1-14 article

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 .

Journal of Combinatorial Theory, Series B (2019) 136: 72-80 article

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.

European Journal of Combinatorics (2018) 72: 29-44 article

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.

Computational Optimization and Applications (2018) 71: 509–523 article

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 .

Geometric and Functional Analysis (2017) 27: 1367-1377 article

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.

Discrete Mathematics (2018) 341: 1597-1604 article

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.

Combinatorics, Probability and Computing (2017) 26: 1-15 article erratum

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.

The Electronic Journal of Combinatorics (2014) 21: P4.39 article