## Preprints

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

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

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

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

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

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