Some aspects of dimension theory for topological groups

We discuss dimension theory in the class of all topological groups. For locally compact topological groups there are many classical results in the literature. Dimension theory for non-locally compact topological groups is mysterious. It is for example unknown whether every connected (hence at least 1-dimensional) Polish group contains a homeomorphic copy of $[0,1]$. And it is unknown whether there is a homogeneous metrizable compact space the homeomorphism group of which is 2-dimensional. Other classical open problems are the following ones. Let $G$ be a topological group with a countable network. Does it follow that $\dim G=\mathrm{ind}G=\mathrm{Ind}G$? The same question if $X$ is a compact coset space. We also do not know whether the inequality $\dim (G\times H)\le \dim G+\dim H$ holds for arbitrary topological groups $G$ and $H$ which are subgroups of $\sigma$-compact topological groups. The aim of this paper is to discuss such and related problems. But we do not attempt to survey the literature.     

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.     

Some results on Vizing’s conjecture and related problems

The well-known conjecture of Vizing on the domination number of Cartesian product graphs claims that for any two graphs $G$ and $H$, $\gamma \left(G\square H\right)\ge \gamma \left(G\right)\gamma \left(H\right)$. We disprove its variations on independent domination number and Barcalkin–German number, i.e. Conjectures 9.6 and 9.2 from the recent survey Bre?ar et al. (2012) [4]. We also give some extensions of the double-projection argument of Clark and Suen (2000) [8], showing that their result can be improved in the case of bounded-degree graphs. Similarly, for rainbow domination number we show for every $k\ge 1$ that ${\gamma }_{rk}\left(G\square H\right)\ge \frac{k}{k+1}\gamma \left(G\right)\gamma \left(H\right)$, which is closely related to Question 9.9 from the same survey. We also prove that the minimum possible counterexample to Vizing’s conjecture cannot have two neighboring vertices of degree two.     

On two Diophantine inequalities over primes

Let $1<c<37∕18,c\ne 2$ and $N$ be a sufficiently large real number. In this paper, we prove that, for almost all $R\in (N,2N]$, the Diophantine inequality $|p_1^c+p_2^c+p_3^c?R|<{log}^{?1}N$ is solvable in primes $p_1,p_2,p_3$. Moreover, we also investigate the problem of six primes and prove that the Diophantine inequality $|p_1^c+p_2^c+p_3^c+p_4^c+p_5^c+p_6^c?N|<{log}^{?1}N$ is solvable in primes $p_1,p_2,p_3,p_4,p_5,p_6$ for sufficiently large real number $N$.     

Improving the Clark–Suen bound on the domination number of the Cartesian product of graphs

A long-standing Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, $\gamma (G\square H)\ge \gamma \left(G\right)\gamma \left(H\right)∕2$, where $\gamma$ stands for the domination number, and $G\square H$ is the Cartesian product of graphs $G$ and $H$. In this note, we improve this bound by employing the 2-packing number $\rho \left(G\right)$ of a graph $G$ into the formula, asserting that $\gamma (G\square H)\ge (2\gamma \left(G\right)?\rho \left(G\right))\gamma \left(H\right)∕3$. The resulting bound is better than that of Clark and Suen whenever $G$ is a graph with $\rho \left(G\right)<\gamma \left(G\right)∕2$, and in the case $G$ has diameter 2 reads as $\gamma (G\square H)\ge (2\gamma \left(G\right)?1)\gamma \left(H\right)∕3$.     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

The multipartite Ramsey number for the 3-path of length three

We study the Ramsey number for the 3-uniform loose path of length three, $P_3^3$, and $n$ colors. We show that $R(P_3^3;n)\le {\lambda }_{0}n+7\sqrt{n}$, for some explicit constant ${\lambda }_0=1.97466\dots$.     

A result on r-orthogonal factorizations in digraphs

Let $G$ be a digraph with vertex set $V\left(G\right)$ and arc set $E\left(G\right)$. Let $m,r,k$ be three positive integers, and let $f=(f^{-},f^{+})$ be a pair of nonnegative integer-valued functions defined on $V\left(G\right)$ with $f\left(x\right)\ge (k+1)r$ for all $x\in V\left(G\right)$. Let $H_1,H_2,\dots ,H_k$ be $k$ vertex disjoint $mr$-subdigraphs of $G$. In this paper, it is proved that every $(0,mf-(m-1)r)$-digraph has a $(0,f)$-factorization $r$-orthogonal to every $H_i$ ($i=1,2,\dots ,k$).     

Orthogonally Resolvable Matching Designs

An orthogonally resolvable matching design OMD$(n,k)$ is a partition of the edges of the complete graph $K_n$ into matchings of size $k$, called blocks, such that the blocks can be resolved in two different ways. Such a design can be represented as a square array whose cells are either empty or contain a matching of size $k$, where every vertex appears exactly once in each row and column. In this paper we show that an OMD$(n,k)$ exists if and only if $n\equiv 0(mod2k)$ except when $k=1$ and $n=4$ or $6$.     

The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.