## Preprints

### On the binary adder channel with complete feedback, with an application to quantitative group testing (with Sam Florin and Matthew Ho )

We determine that the average zero-error capacity of the binary adder channel with complete feedback is $$h(1/2-\delta)$$, where $$h$$ is the binary entropy function and $$\delta = 1/(2\log_2(2+\sqrt3))$$.

### Rainbow odd cycles (with Ron Aharoni, Joseph Briggs and Ron Holzman )

Every family of odd cycles $$O_1, \dots, O_{2\lceil n/2 \rceil - 1}$$ in the complete graph on $$n$$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $$O_i$$’s, forming an odd cycle).

### Negligible obstructions and Turán exponents (with Tao Jiang and Jie Ma )

For every rational number $$r \in (1,2)$$ of the form $$2 - a/b$$, where $$a, b \in \mathbb{N}^+$$ satisfy $$\lfloor b/a \rfloor^3 \le a \le b / (\lfloor b/a \rfloor +1) + 1$$, there exists a graph $$F_r$$ such that the Turán number $$\operatorname{ex}(n, F_r) = \Theta(n^r)$$.

### Spherical two-distance sets and eigenvalues of signed graphs (with Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao )

For fixed $$-1 \le \beta < 0 \le \alpha < 1$$, let $$N_{\alpha, \beta}(d)$$ denote the maximum number of unit vectors in $$\mathbb{R}^d$$ where all pairwise inner products lie in $$\{\alpha, \beta\}$$. We determine the limit of $$N_{\alpha, \beta}(d)/d$$ as $$d \to \infty$$ when $$\alpha + 2\beta < 0$$ or $$(1-\alpha)/(\alpha - \beta) \in \{1,\sqrt{2},\sqrt{3}\}$$.

### Equiangular lines with a fixed angle (with Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao )

We determine the maximum cardinality $$N_{\alpha}(n)$$ of lines pairwise separated by the angle $$\arccos\alpha$$ in $$\mathbb{R}^n$$ for every $$\alpha$$ and all sufficiently large $$n$$. In particular, $$N_{1/(2k-1)}(n) = \lfloor k(n-1)/(k-1) \rfloor$$ for every integer $$k \ge 2$$ and all sufficiently large $$n$$.

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

Denote by $$\mathcal{B}_n(R)$$ the $$n$$-dimensional Hamming ball of radius $$R$$. If $$n/4 \le R \le n/2$$ and the size of a subset $$\mathcal{A}$$ of $$\mathcal{B}_n(R)$$ satisfies $$\vert\mathcal{B}_n(n/4)\vert \le \vert\mathcal{A}\vert \le \tfrac{1}{2}\vert\mathcal{B}_n(R)\vert$$, then the vertex boundary of $$\mathcal{A}$$ is at least $$\Omega(\vert\mathcal{A}\vert/\sqrt{n})$$.

## Publication

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

Given a system $$\mathcal{G}=(G_1, \ldots ,G_m)$$ of graphs on the same vertex set $$V$$, a cooperative coloring for $$\mathcal{G}$$ is a choice of vertex sets $$I_1, \ldots ,I_m$$, such that $$I_j$$ is independent in $$G_j$$ and $$\bigcup_{j=1}^{m}I_j = V$$. We give bounds on the minimal $$m$$ such that every $$m$$ graphs with maximum degree $$d$$ have a cooperative coloring, in the cases that (a) the graphs are trees, (b) the graphs are all bipartite.

The Electronic Journal of Combinatorics (2020) 27: P1.41 article

### Rainbow fractional matchings (with Ron Aharoni and Ron Holzman )

Any family $$E_1, \dots, E_{\lceil rn\rceil}$$ of sets of edges in an $$r$$-uniform hypergraph, each having a fractional matchings number of size $$n$$, has a rainbow matching of size $$n$$ (that is, a set of edges from distinct $$E_i$$’s which supports such a fractional matching).

Combinatorica (2019) 39: 1191-1202 article

### 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 $$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$$.

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

### 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)$$.

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 $$\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.

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

### 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 $$\le \lambda$$ has a finite forbidden subgraphs characterization if and only if $$\lambda < \lambda^*$$ and $$\lambda \not\in \{\alpha_2, \alpha_3, \ldots\}$$, where $$\alpha_m = \beta_m^{1/2} + \beta_m^{-1/2}$$ and $$\beta_m$$ is the largest root of $$x^{m+1} = 1 + x + \ldots + x^{m-1}$$. 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^*}$$.

Israel Journal of Mathematics (2020) 236: 393–421 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 $$\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$$.

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 $$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.

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 $$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.

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

### 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.

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