Search

We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$'s, forming an odd cycle). As part of the proof, we characterize those families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any rainbow cycle., 14 pages, 2 figures, accepted to SIAM Journal on Discrete Mathematics (SIDMA)

We prove that any family $E_1, \ldots , E_{\lceil rn \rceil}$ of (not necessarily distinct) sets of edges in an $r$-uniform hypergraph, each having a fractional matching of size $n$, has a rainbow fractional matching of size $n$ (that is, a set of edges from distinct $E_i$'s which supports such a fractional matching). When the hypergraph is $r$-partite and $n$ is an integer, the number of sets needed goes down from $rn$ to $rn-r+1$. The problem solved here is a fractional version of the corresponding problem about rainbow matchings, which was solved by Drisko and by Aharoni and Berger in the case of bipartite graphs, but is open for general graphs as well as for $r$-partite hypergraphs with $r>2$. Our topological proof is based on a result of Kalai and Meshulam about a simplicial complex and a matroid on the same vertex set., 10 pages, accepted to Combinatorica, corrections suggested by the referees have been incorporated

Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$, a cooperative coloring 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$. For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $\Omega(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $\Omega(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$, where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs., Comment: 8 pages, 2 figures, accepted to the Electronic Journal of Combinatorics, corrections suggested by the referees have been incorporated

Let $\mathbb{P}^s$ be the $s$-dimensional complex projective space, and let $X, Y$ be two non-empty open subsets of $\mathbb{P}^s$ in the Zariski topology. A hypersurface $H$ in $\mathbb{P}^s\times\mathbb{P}^s$ induces a bipartite graph $G$ as follows: the partite sets of $G$ are $X$ and $Y$, and the edge set is defined by $\overline{u}\sim\overline{v}$ if and only if $(\overline{u},\overline{v})\in H$. Motivated by the Tur\'an problem for bipartite graphs, we say that $H\cap (X\times Y)$ is $(s,t)$-grid-free provided that $G$ contains no complete bipartite subgraph that has $s$ vertices in $X$ and $t$ vertices in $Y$. We conjecture that every $(s,t)$-grid-free hypersurface is equivalent, in a suitable sense, to a hypersurface whose degree in $\overline{y}$ is bounded by a constant $d = d(s,t)$, and we discuss possible notions of the equivalence. We establish the result that if $H\cap(X\times \mathbb{P}^2)$ is $(2,2)$-grid-free, then there exists $F\in \mathbb{C}[\overline{x},\overline{y}]$ of degree $\le 2$ in $\overline{y}$ such that $H\cap(X\times \mathbb{P}^2) = \{F = 0\}\cap (X\times \mathbb{P}^2)$. Finally, we transfer the result to algebraically closed fields of large characteristic., Comment: 13 pages, accepted to Discrete Math., corrections suggested by the referees have been incorporated

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$, answering a question of Fejes T\'oth from 1973., Comment: 10 pages, 3 figures, this version adds some conjectures, accepted to Geom. Funct. Anal., corrections suggested by the referees have been incorporated

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle. Fix $0 < \alpha < 1$. Let $N_\alpha(d)$ denote the maximum number of lines through the origin in $\mathbb{R}^d$ with pairwise common angle $\arccos \alpha$. Let $k$ denote the minimum number (if it exists) of vertices in a graph whose adjacency matrix has spectral radius exactly $(1-\alpha)/(2\alpha)$. If $k < \infty$, then $N_\alpha(d) = \lfloor k(d-1)/(k-1) \rfloor$ for all sufficiently large $d$, and otherwise $N_\alpha(d) = d + o(d)$. In particular, $N_{1/(2k-1)}(d) = \lfloor k(d-1)/(k-1) \rfloor$ for every integer $k\ge 2$ and all sufficiently large $d$. A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity., Comment: 11 pages. Fixed a minor issue at the end of the proof of Theorem 1.2

The exact values of the optimal symmetric rate point in the Cover--Leung capacity region of the two-user union channel with complete feedback were determined by Willems when the size of the input alphabet is 2, and by Vinck, Hoeks and Post when the size is at least 6. We complete this line of research when the size of the input alphabet is 3, 4 or 5. The proof hinges on the technical lemma that concerns the maximal joint entropy of two independent random variables in terms of their probability of equality. For the zero-error capacity region, using superposition coding, we provide a practical near-optimal communication scheme which improves all the previous explicit constructions., 16 pages, 1 figure, 1 table, accepted to IEEE Trans. Inf. Theory, corrections suggested by the referees have been incorporated

Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern--Lions--Wittmann--Bauschke algorithm for approaching the projection of a given point onto a convex set., 14 pages, 8 figures, accepted to Computational Optimization and Applications (COAP)

The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Let $\mathcal{F}(\lambda)$ be the family of connected graphs of spectral radius $\le \lambda$. We show that $\mathcal{F}(\lambda)$ can be defined by a finite set of forbidden subgraphs if and only if $\lambda < \lambda^* := \sqrt{2+\sqrt{5}} \approx 2.058$ and $\lambda \not\in \{\alpha_2, \alpha_3, \dots\}$, where $\alpha_m = \beta_m^{1/2} + \beta_m^{-1/2}$ and $\beta_m$ is the largest root of $x^{m+1}=1+x+\dots+x^{m-1}$. The study of forbidden subgraphs characterization for $\mathcal{F}(\lambda)$ is motivated by the problem of estimating the maximum cardinality of equiangular lines in the $n$-dimensional Euclidean space $\mathbb{R}^n$ --- a family of lines through the origin such that the angle between any pair of them is the same. Denote by $N_\alpha(n)$ the maximum number of equiangular lines in $\mathbb{R}^n$ with angle $\arccos\alpha$. We establish the asymptotic formula $N_\alpha(n) = c_\alpha n + O_\alpha(1)$ for every $\alpha \ge \frac{1}{1+2\lambda^*}$. In particular, $N_{1/3}(n) = 2n+O(1)$ and $N_{1/5}(n), N_{1/(1+2\sqrt{2})}(n) = \frac{3}{2}n+O(1)$. Besides we show that $N_\alpha(n) \le 1.49n + O_\alpha(1)$ for every $\alpha \neq \tfrac{1}{3}, \tfrac{1}{5}, \tfrac{1}{1+2\sqrt{2}}$, which improves a recent result of Balla, Dr\"axler, Keevash and Sudakov., Comment: 23 pages, this version fixes an error in Theorem 1, accepted to Israel J. Math., corrections suggested by the referee have been incorporated

Given a graph $G$, the unraveled ball of radius $r$ centered at a vertex $v$ is the ball of radius $r$ centered at $v$ in the universal cover of $G$. We prove a lower bound on the maximum spectral radius of unraveled balls of fixed radius, and we show, among other things, that 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(\frac{\pi}{r+1})$., Comment: 8 pages, accepted to J. Comb. Theory B, corrections suggested by the referees have been incorporated

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. Fix a connected graph $G$ on $q \ge 2$ vertices, and let $M$ be the distance matrix of $G$. We prove that if there exists $w \in \mathbb{Z}^q$ such that $\sum_i w_i = 0$ and the vector $Mw$, after sorting its coordinates, is an arithmetic progression with nonzero common difference, then the metric dimension of the Cartesian product of $n$ copies of $G$ is $(2+o(1))n/\log_q n$. In the special case that $G$ is a complete graph, our results close the gap between the lower bound attributed to Erd\H{o}s and R\'enyi and the upper bounds developed subsequently by Lindstr\"om, Chv\'atal, Kabatianski, Lebedev and Thorpe., Comment: 12 pages, 1 figure, 1 table, accepted to J. Comb. Theory A, corrections suggested by the referees have been incorporated

Due to a calculation error, the constant in the main theorem is not $80 \sqrt{k\log k}$ but $80\sqrt{k} \log k$. The error was discovered by Xizhi Liu.For a new discussion on the limit of the method used in this paper see the revised arXiv version of the paper.

Suppose $d+1$ absolutely continuous probability measures $m_0, \ldots, m_d$ on $\mathbb{R}^d$ are given. In this paper, we prove that there exists a point of $\mathbb{R}^d$ that belongs to the convex hull of $d+1$ points $v_0, \ldots, v_d$ with probability at least $\frac{2d}{(d+1)!(d+1)}$, where each point $v_i$ is sampled independently according to probability measure $m_i$., Comment: 8 pages, 5 figures, published, Electron. J. Combin., corrections suggested by the referee have been incorporated

We show that, 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., Comment: 16 pages, v2 appeared in Comb. Probab. Comp., v3 fixes an error in v2 and explains why the method in the paper cannot improve the power of k further, v4 fixes the proof of Theorem 12 introduced in v3