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})\).


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