Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

Schatten properties,nuclearity and minimality of phase shift invariant spaces

We extend Feichtinger's minimality property on the smallest non-trivial time-frequency shift invariant Banach space, to the quasi-Banach case. Analogous properties are deduced for certain matrix spaces.We use these results to prove that the pseudo-differential operator $\mathrm{Op}(a)$ is a Schatten-q operator from $M^{\infty }$ to $M^p$ and r-nuclear operator from $M^{\infty }$ to $M^r$ when $a\in M^r$ for suitable p, q and r in $(0,\infty ]$.     

Bounds for the Graham–Pollak theorem for hypergraphs

Let $f_r\left(n\right)$ represent the minimum number of complete $r$-partite $r$-graphs required to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. The Graham–Pollak theorem states that $f_2\left(n\right)=n?1$. An upper bound of $(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was known. Recently this was improved to $\frac{14}{15}(1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ for even $r\ge 4$. A bound of $\left[\frac{r}{2}{\left(\frac{14}{15}\right)}^{\frac{r}{4}}+o\left(1\right)\right](1+o\left(1\right))\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)$ was also proved recently. Let $c_r$ be the limit of $\frac{f_r\left(n\right)}{\left(\genfrac{}{}{0ex}{}{n}{?\frac{r}{2}?}\right)}$ as $n\to \infty$. The smallest odd $r$ for which $c_r<1$ that was known was for $r=295$. In this note we improve this to $c_{113}<1$ and also give better upper bounds for $f_r\left(n\right)$, for small values of even $r$.     

On generalized Erdős–Ginzburg–Ziv constants of Cnr

Let $G$ be an additive finite abelian group with exponent $exp\left(G\right)=n$. For any positive integer $k$, the $k$th Erdős–Ginzburg–Ziv constant ${\mathsf{s}}_{kn}\left(G\right)$ is defined as the smallest positive integer $t$ such that every sequence $S$ in $G$ of length at least $t$ has a zero-sum subsequence of length $kn$. It is easy to see that ${\mathsf{s}}_{kn}\left(C_n^r\right)\ge (k+r)n-r$ where $n,r\in \mathbb{N}$. Kubertin conjectured that the equality holds for any $k\ge r$. In this paper, we prove the following results:

• •[(1)] For every positive integer $k\ge 6$, we have ${\mathsf{s}}_{kn}\left(C_n^3\right)=(k+3)n+O\left(\frac{n}{lnn}\right).$
• •[(2)] For every positive integer $k\ge 18$, we have ${\mathsf{s}}_{kn}\left(C_n^4\right)=(k+4)n+O\left(\frac{n}{lnn}\right).$
• •[(3)] For $n\in \mathbb{N}$, assume that the largest prime power divisor of $n$ is $p^a$ for some $a\in \mathbb{N}$. Forany fixed $r\ge 5$, if $p^t\ge r$ for some $t\in \mathbb{N}$, then for any $k\in \mathbb{N}$ we have ${\mathsf{s}}_{k{p}^{t}n}\left(C_n^r\right)\le (k{p}^t+r)n+c_r\frac{n}{lnn},$where $c_r$ is a constant that depends on $r$.

Our results verify the conjecture of Kubertin asymptotically in the above cases.     

Relation between the H-rank of a mixed graph and the rank of its underlying graph

Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $\stackrel{?}{G}$ is obtained from $G$ by orienting some of its edges. Let $H\left(\stackrel{?}{G}\right)$ denote the Hermitian adjacency matrix of $\stackrel{?}{G}$ and $A\left(G\right)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $\stackrel{?}{G}$ (resp. $G$), written as $rk\left(\stackrel{?}{G}\right)$ (resp. $r\left(G\right)$), is the rank of $H\left(\stackrel{?}{G}\right)$ (resp. $A\left(G\right)$). Denote by $d\left(G\right)$ the dimension of cycle space of $G$, that is $d\left(G\right)=\left|E_G\right|?\left|V_G\right|+\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $\stackrel{?}{G}$ and the rank of $G$. We first show that $?2d\left(G\right)?rk\left(\stackrel{?}{G}\right)?r\left(G\right)?2d\left(G\right)$ for every mixed graph $\stackrel{?}{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently.     

Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G\left(1\right),\dots ,G\left(k\right)$. It is called an $r$-factorization if every $G\left(i\right)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1\le i\le k$, $G\left(i\right)$ is a subgraph of $H\left(i\right)$.Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some 2-edge-connected $r$-factorization of $\mu K_m$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu >\lambda$ and either $m\ge 2n?1$, or $m=2n?2$ and $\mu =2$ and $\lambda =1$, or $n=3$ and $m=4$. We generalize their result to every $r\ge 2$ and $m\ge 2n?2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some 2-edge-connected $r$-factorization of $\mu K_m$ for every $r\ge 3$ and $m>(2?C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and $\mu$.     

Diffusive search with spatially dependent resetting

We consider a stochastic search model with resetting for an unknown stationary target $a\in \mathbb{R}$ with known distribution $\mu$. The searcher begins at the origin and performs Brownian motion with diffusion constant $D$. The searcher is also armed with an exponential clock with spatially dependent rate $r=r\left(\cdot \right)$, so that if it has failed to locate the target by the time the clock rings, then its position is reset to the origin and it continues its search anew from there. Denote the position of the searcher at time $t$ by $X\left(t\right)$. Let $E_0^{\left(r\right)}$ denote expectations for the process $X\left(\cdot \right)$. The search ends at time $T_a=inf\{t\ge 0:X\left(t\right)=a\}$. The expected time of the search is then ${\int }_{\mathbb{R}}\left(E_0^{\left(r\right)}{T}_a\right)\mu \left(da\right)$. Ideally, one would like to minimize this over all resetting rates $r$. We obtain quantitative growth rates for $E_0^{\left(r\right)}{T}_a$ as a function of $a$ in terms of the asymptotic behavior of the rate function $r$, and also a rather precise dichotomy on the asymptotic behavior of the resetting function $r$ to determine whether $E_0^{\left(r\right)}{T}_a$ is finite or infinite. We show generically that if $r\left(x\right)$ is of the order ${\left|x\right|}^{2l}$, with $l>-1$, then $log{E}_0^{\left(r\right)}{T}_a$ is of the order ${\left|a\right|}^{l+1}$; in particular, the smaller the asymptotic size of $r$, the smaller the asymptotic growth rate of $E_0^{\left(r\right)}{T}_a$. The asymptotic growth rate of $E_0^{\left(r\right)}{T}_a$ continues to decrease when $r\left(x\right)\sim \frac{D\lambda }{x^2}$ with $\lambda >1$; now the growth rate of $E_0^{\left(r\right)}{T}_a$ is more or less of the order ${\left|a\right|}^{\frac{1+\sqrt{1+8\lambda }}{2}}$. Note that this exponent increases to $\infty$ when $\lambda$ increases to $\infty$ and decreases to 2 when $\lambda$ decreases to 1. However, if $\lambda =1$, then $E_0^{\left(r\right)}{T}_a=\infty$, for $a\ne 0$. Our results suggest that for many distributions $\mu$ supported on all of $\mathbb{R}$, a near optimal (or optimal) choice of resetting function $r$ in order to minimize ${\int }_{{\mathbb{R}}^d}\left(E_0^{\left(r\right)}{T}_a\right)\mu \left(da\right)$ will be one which decays quadratically as $\frac{D\lambda }{x^2}$ for some $\lambda >1$. We also give explicit, albeit rather complicated, variational formulas for ${inf}_{r\gneqq 0}{\int }_{{\mathbb{R}}^d}\left(E_0^{\left(r\right)}{T}_a\right)\mu \left(da\right)$. For distributions $\mu$ with compact support, one should set $r=\infty$ off of the support. We also discuss this case.     

Graph homomorphisms via vector colorings

In this paper we study the existence of homomorphisms $G\to H$ using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number $t\ge 2$ for which there exists an assignment of unit vectors $i\mapsto p_i$ to its vertices such that $〈p_i,p_j〉\le -1∕(t-1),$ when $i\sim j$. Our approach allows to reprove, without using the Erdős–Ko–Rado Theorem, that for $n>2r$ the Kneser graph $K_{n:r}$ and the $q$-Kneser graph $q{K}_{n:r}$ are cores, and furthermore, that for $n∕r=n^{\prime }∕r^{\prime }$ there exists a homomorphism $K_{n:r}\to K_{n^{\prime }:r^{\prime }}$ if and only if $n$ divides $n^{\prime }$. In terms of new applications, we show that the even-weight component of the distance $k$-graph of the $n$-cube $H_{n,k}$ is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms $H_{n,k}\to H_{n^{\prime },k^{\prime }}$ when $n∕k=n^{\prime }∕k^{\prime }$. Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence’s list of strongly regular graphs (http://www.maths.gla.ac.uk/ es/srgraphs.php) and found that at least 84% are cores.     

Exponential lower bounds on the generalized Erdős–Ginzburg–Ziv constant

For a finite abelian group $G$, the generalized Erdős–Ginzburg–Ziv constant ${\mathsf{s}}_k\left(G\right)$ is the smallest $m$ such that a sequence of $m$ elements in $G$ always contains a $k$-element subsequence which sums to zero. If $n=exp\left(G\right)$ is the exponent of $G$, the previously best known bounds for ${\mathsf{s}}_{kn}\left(C_n^r\right)$ were linear in $n$ and $r$ when $k\ge 2$. Via a probabilistic argument, we produce the exponential lower bound ${\mathsf{s}}_{2n}\left(C_n^r\right)>\frac{n}{2}{[1.25+o\left(1\right)]}^r$for $n>0$. For the general case, we show ${\mathsf{s}}_{kn}\left(C_n^r\right)>\frac{kn}{4}{\left(1+\frac{1}{ek+1}+o\left(1\right)\right)}^r.$