Vertex-disjoint cycles in regular tournaments

The Bermond–Thomassen conjecture states for $r\ge 1$, any digraph of minimum out-degree at least $2r?1$ contains at least $r$ vertex-disjoint directed cycles. In a recent paper, Bessy, Sereni and the author proved that a regular tournament $T$ of degree $2r?1$ contains at least $r$ vertex-disjoint directed cycles, which shows that the above conjecture is true for regular tournaments. In this paper, we improve this result by proving that such a tournament contains at least $\frac{7}{6}r?\frac{7}{3}$ vertex-disjoint directed cycles.     

The 2-center problem in three dimensions

Let P be a set of n points in ${\mathbb{R}}^3$. The 2-center problem for P is to find two congruent balls of minimum radius whose union covers P. We present a randomized algorithm for computing a 2-center of P that runs in $O(\beta (r^{?})n^2{\log }^{4}n\log \log n)$ expected time; here $\beta (r)=1/{(1?r/r_0)}^3$, $r^{?}$ is the radius of the 2-center balls of P, and $r_0$ is the radius of the smallest enclosing ball of P. The algorithm is near quadratic as long as $r^{?}$ is not too close to $r_0$, which is equivalent to the condition that the centers of the two covering balls be not too close to each other. This improves an earlier slightly super-cubic algorithm of Agarwal, Efrat, and Sharir (2000) [2] (at the cost of making the algorithm performance depend on the center separation of the covering balls).     

On the sum of reciprocals of least common multiples

Let ${\{a_i\}}_{i=1}^{\infty }$ be a strictly increasing sequence of positive integers ($a_i<a_j$ if $i<j$). In 1978, Borwein showed that for any positive integer n, we have ${\sum }_{i=1}^n\frac{1}{\mathrm{lcm}(a_i,a_{i+1})}\le 1?\frac{1}{2^n}$, with equality occurring if and only if $a_i=2^{i?1}$ for $1\le i\le n+1$. Let $3\le r\le 7$ be an integer. In this paper, we investigate the sum ${\sum }_{i=1}^n\frac{1}{\mathrm{lcm}(a_i,...,a_{i+r?1})}$ and show that ${\sum }_{i=1}^n\frac{1}{\mathrm{lcm}(a_i,...,a_{i+r?1})}\le U_r(n)$ for any positive integer n, where $U_r(n)$ is a constant depending on r and n. Further, for any integer $n\ge 2$, we also give a characterization of the sequence ${\{a_i\}}_{i=1}^{\infty }$ such that the equality ${\sum }_{i=1}^n\frac{1}{\mathrm{lcm}(a_i,...,a_{i+r?1})}=U_r(n)$ holds.     

Powerful numbers in (1ℓ + qℓ)(2ℓ + qℓ)⋯(nℓ + qℓ)

Let q be a positive integer. Recently, Niu and Liu proved that, if $n\ge \max ?\{q,1198?q\}$, then the product $(1^3+q^3)(2^3+q^3)?(n^3+q^3)$ is not a powerful number. In this note, we prove (1) that, for any odd prime power ? and $n\ge \max ?\{q,11?q\}$, the product $(1^{?}+q^{?})(2^{?}+q^{?})?(n^{?}+q^{?})$ is not a powerful number, and (2) that, for any positive odd integer ?, there exists an integer $N_{q,?}$ such that, for any positive integer $n\ge N_{q,?}$, the product $(1^{?}+q^{?})(2^{?}+q^{?})?(n^{?}+q^{?})$ is not a powerful number.     

Turán numbers for odd wheels

The Turán number $\text{ex}(n,G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A wheel$W_n$ is a graph on $n$ vertices obtained from a $C_{n?1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n?1}$. We obtain two exact values for small wheels:

$\text{ex}(n,W_5)=?\frac{n^2}{4}+\frac{n}{2}?,$

$\text{ex}(n,W_7)=?\frac{n^2}{4}+\frac{n}{2}+1?.$

Given that $\text{ex}(n,W_6)$ is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound $\text{ex}(n,W_{2k+1})>?\frac{n^2}{4}?+?\frac{n}{2}?$ in general case.     

Covering complete partite hypergraphs by monochromatic components

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson (1971)) states that $k$-partite intersecting hypergraphs have transversals of at most $k?1$ vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in Gyárfás (1977): if the edges of a complete graph $K$ are colored with $k$ colors then the vertex set of $K$ can be covered by at most $k?1$ sets, each forming a connected graph in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: it was proved in Király (2013) that in every $k$-coloring of the edges of the $r$-uniform complete hypergraph $K^r$ ($r\ge 3$), the vertex set of $K^r$ can be covered by at most $?k∕r?$ sets, each forming a connected hypergraph in some color.Here we investigate the analogue problem for complete $r$-uniform $r$-partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of every color used in the coloring. We propose the following analogue of Ryser’s conjecture.In every spanning $(r+t)$-coloring of the edges of a complete $r$-uniform $r$-partite hypergraph, the vertex set can be covered by at most $t+1$ sets, each forming a connected hypergraph in some color.We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for $1\le t\le r?1$. We also prove a slightly weaker result for $t\ge r$, namely that $t+2$ sets, each forming a connected hypergraph in some color, are enough to cover the vertex set.To build a bridge between complete $r$-uniform and complete $r$-uniform $r$-partite hypergraphs, we introduce a new notion. A hypergraph is complete $r$-uniform $(r,?)$-partite if it has all $r$-sets that intersect each partite class in at most $?$ vertices (where $1\le ?\le r$).Extending our results achieved for $?=1$, we prove that for any $r\ge 3,2\le ?\le r,k\ge 1+r??$, in every spanning $k$-coloring of the edges of a complete $r$-uniform $(r,?)$-partite hypergraph, the vertex set can be covered by at most $1+?\frac{k?r+??1}{?}?$ sets, each forming a connected hypergraph in some color.     

The anti-Ramsey number of perfect matching

An $r$-edge coloring of a graph $G$ is a mapping $h:E\left(G\right)\to \left[r\right]$, where $h\left(e\right)$ is the color assigned to edge $e\in E\left(G\right)$. An exact $r$-edge coloring is an $r$-edge coloring $h$ such that there exists an $e\in E\left(G\right)$ with $h\left(e\right)=i$ for all $i\in \left[r\right]$. Let $h$ be an edge coloring of $G$. We say $G$ is rainbow if no two edges in $G$ are assigned the same color by $h$. The anti-Ramsey number, $AR(G,n)$, is the smallest integer $r$ such that for any exact $r$-edge coloring of $K_n$ there exists a subgraph isomorphic to $G$ that is rainbow. In this paper we confirm a conjecture of Fujita, Kaneko, Schiermeyer, and Suzuki that states $AR(M_k,2k)=max\{\left(\genfrac{}{}{0ex}{}{2k?3}{2}\right)+3,\left(\genfrac{}{}{0ex}{}{k?2}{2}\right)+k^2?2\}$, where $M_k$ is a matching of size $k\ge 3$.     

Diffuse reflection diameter and radius for convex-quadrilateralizable polygons

In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons. In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon $P$ is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point $t$ from any point light source $s$ inside $P$. We show that the diameter is upper bounded by $\frac{3n?10}{4}$ in our usual model of diffuse reflection for convex-quadrilateralizable polygons. To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of $n$ for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with $n$ vertices is at most $\frac{3n?10}{8}$ under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which $\frac{3n?10}{8}$ usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are $\frac{n?4}{2}$ and $?\frac{n?4}{4}?$ respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of $\frac{n?4}{2}$ and $?\frac{n?4}{4}?$ respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection.     

Congruences modulo powers of 3 for 3- and 9-colored generalized Frobenius partitions

Let $c{?}_k\left(n\right)$ be the number of $k$-colored generalized Frobenius partitions of $n$. We establish some infinite families of congruences for $c{?}_3\left(n\right)$ and $c{?}_9\left(n\right)$ modulo arbitrary powers of 3, which refine the results of Kolitsch. For example, for $k\ge 3$ and $n\ge 0$, we prove that

$c{?}_3\left(3^{2k}n+\frac{7?3^{2k}+1}{8}\right)\equiv 0(mod{3}^{4k+5}).$

We give two different proofs to the congruences satisfied by $c{?}_9\left(n\right)$. One of the proofs uses a relation between $c{?}_9\left(n\right)$ and $c{?}_3\left(n\right)$ due to Kolitsch, for which we provide a new proof in this paper.