Preprints
Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below
(with
Alexandr Polyanskii
)
We show that the family of graphs with smallest eigenvalue at least \(-\lambda\) has a finite forbidden subgraphs characterization if and only if \(\lambda < \lambda^*\), where \(\lambda^* = \beta^{1/2} + \beta^{-1/2}\) and \(\beta\) is the unique real root of \(x^3 = 1 + x\). We also prove the same conclusion for signed graphs. As a consequence, we establish the asymptotic formula of the maximum cardinality of spherical two-distance set with two fixed inner products \(\alpha\) and \(\beta\) for all \(-1 \le \beta < 0 \le \alpha < 1\) satisfying \((1-\alpha)/(\alpha-\beta) < \lambda^*\).
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}\}\).
Publication
On the binary adder channel with complete feedback, with an application to quantitative group testing
(with
Sam H. Florin
and
Matthew H. 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))\).
IEEE Transactions on Information Theory (2022) 68, 2839-2856
article
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).
SIAM Journal on Discrete Mathematics (2020) 35, 2293-2303
article
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)\).
Annals of Applied Mathematics (2022) 38: 356-384
article
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\).
Annals of Mathematics (2021) 194: 729-743
article
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})\).
The Electronic Journal of Combinatorics (2022) 29: P1.15
article
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