Path decompositions of triangle-free graphs

Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then $p(G)\le ?n/2?$. If G is allowed to be disconnected, then the upper bound $?\frac{3}{4}n?$ for $p(G)$ was obtained by Donald [7], which was improved to $?\frac{2}{3}n?$ independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, $?\frac{2}{3}n?$ is reached and so this bound is tight. If triangles are forbidden in G, then $p(G)\le ?\frac{g+1}{2g}n?$ can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that $p(G)\le ?3n/5?$, which improves the above result with $g=4$.     

A plurality problem with three colors and query size three

The Plurality problem - introduced by Aigner - has many variants. In this article we deal with the following version: suppose we are given n balls, each of them colored by one of three colors. A plurality ball is one such that its color class is strictly larger than any other color class. Questioner asks a triplet (or a k-set in general), and Adversary as an answer gives the partition of the triplet (or the k-set) into color classes. Questioner wants to find a plurality ball as soon as possible or show that there is no such ball, while Adversary wants to postpone this.We denote by $A_p(n,k)$ the largest number of queries needed to ask in the worst case if both play optimally. We provide an almost precise result in the case of even n by proving that for $n\ge 4$ even we have$\frac{3}{4}n?2\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2},$ and for $n\ge 3$ odd we have$\frac{3}{4}n?O(\log ?n)\le A_p(n,3)\le \frac{3}{4}n?\frac{1}{2}.$We also prove some bounds on the number of queries needed to ask in the case $k\ge 3$.     

A note on the distribution of weights of fixed-rank matrices over the binary field

Let M be a random $m\times n$ rank-r matrix over the binary field ${\mathbb{F}}_2$, and let $\mathrm{wt}(\mathbf{M})$ be its Hamming weight, that is, the number of nonzero entries of M.We prove that, as $m,n\to +\infty$ with r fixed and $m/n$ tending to a constant, we have that$\frac{\mathrm{wt}(\mathbf{M})-\frac{1-2^{-r}}{2}mn}{\sqrt{\frac{2^{-r}(1-2^{-r})}{4}(m+n)mn}}$ converges in distribution to a standard normal random variable.     

Solutions for conformally invariant fractional Laplacian equations with multi-bumps centered in lattices

In this paper, we consider the following nonlinear elliptic equation involving the fractional Laplacian with critical exponent:

${(?\mathrm{\Delta })}^{s}u=K(x)u^{\frac{N+2s}{N?2s}},u>0\mathrm{in}{\mathbb{R}}^N,$

where $s\in (0,1)$ and $N>2+2s$, $K>0$ is periodic in $(x_1,\dots ,x_k)$ with $1\le k<\frac{N?2s}{2}$. Under some natural conditions on K near a critical point, we prove the existence of multi-bump solutions where the centers of bumps can be placed in some lattices in ${\mathbb{R}}^k$, including infinite lattices. On the other hand, to obtain positive solution with infinite bumps such that the bumps locate in lattices in ${\mathbb{R}}^k$, the restriction on $1\le k<\frac{N?2s}{2}$ is in some sense optimal, since we can show that for $k\ge \frac{N?2s}{2}$, no such solutions exist.     

Domination versus total domination in claw-free cubic graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, while the total domination number ${\gamma }_t(G)$ of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then $\frac{{\gamma }_t(G)}{\gamma (G)}\le \frac{12}{7}$, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then ${\gamma }_t(G)\le \frac{3}{7}n$, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].     

Note on rainbow cycles in edge-colored graphs

Let G be a graph of order n with an edge-coloring c, and let ${\delta }^c(G)$ denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if ${\delta }^c(G)>\frac{2n?1}{3}$, then every vertex of G is contained in a rainbow triangle; (ii) if ${\delta }^c(G)>\frac{2n?1}{3}$ and $n\ge 13$, then every vertex of G is contained in a rainbow $C_4$; (iii) if G is complete, $n\ge 7k?17$ and ${\delta }^c(G)>\frac{n?1}{2}+k$, then G contains a rainbow cycle of length at least k, where $k\ge 5$.     

On the concentration phenomenon of L2-subcritical constrained minimizers for a class of Kirchhoff equations with potentials

In this paper, we study the existence and concentration behavior of minimizers for $i_V(c)=\underset{u\in S_c}{\inf }?I_V(u)$, here $S_c=\{u\in H^1({\mathbb{R}}^N)|{\int }_{{\mathbb{R}}^N}V(x)|u{|}^2<+\infty ,|u{|}_2=c>0\}$ and

$I_V(u)=\frac{1}{2}\underset{{\mathbb{R}}^N}{\int }(a|\mathrm{?}u{|}^2+V(x)|u{|}^2)+\frac{b}{4}{(\underset{{\mathbb{R}}^N}{\int }|\mathrm{?}u{|}^2)}^2?\frac{1}{p}\underset{{\mathbb{R}}^N}{\int }|u{|}^p,$

where $N=1,2,3$ and $a,b>0$ are constants. By the Gagliardo–Nirenberg inequality, we get the sharp existence of global constraint minimizers of $i_V(c)$ for $2<p<2^{?}$ when $V(x)\ge 0$, $V(x)\in {L^{\infty }}_{loc}({\mathbb{R}}^N)$ and $\underset{|x|\to +\infty }{\lim }?V(x)=+\infty$. For the case $p\in (2,\frac{2N+8}{N})\backslash \{4\}$, we prove that the global constraint minimizers $u_c$ of $i_V(c)$ behave like

$u_c(x)\approx \frac{c}{|Q_p{|}_2}{\left(\frac{m_c}{c}\right)}^{\frac{N}{2}}{Q}_p(\frac{m_c}{c}x?z_c),$

for some $z_c\in {\mathbb{R}}^N$ when c is large, where $Q_p$ is, up to translations, the unique positive solution of $?\frac{N(p?2)}{4}\mathrm{\Delta }{Q}_p+\frac{2N?p(N?2)}{4}{Q}_p=|Q_p{|}^{p?2}{Q}_p$ in ${\mathbb{R}}^N$ and $m_c={(\frac{\sqrt{a^2{D}_1^2?4b{D}_2{i}_0(c)}+a{D}_1}{2b{D}_2})}^{\frac{1}{2}}$, $D_1=\frac{Np?2N?4}{2N(p?2)}$ and $D_2=\frac{2N+8?Np}{4N(p?2)}$.     

Compactness of sign-changing solutions to scalar curvature-type equations with bounded negative part

We consider the equation ${\mathrm{\Delta }}_{g}u+hu=|u{|}^{2^{?}?2}u$ in a closed Riemannian manifold $(M,g)$, where $h\in C^{0,\theta }(M)$, $\theta \in (0,1)$ and $2^{?}=\frac{2n}{n?2}$, $n:=\dim ?(M)\ge 3$. We obtain a sharp compactness result on the sets of sign-changing solutions whose negative part is a priori bounded. We obtain this result under the conditions that $n\ge 7$ and $h<\frac{n?2}{4(n?1)}{\text{Scal}}_g$ in M, where ${\text{Scal}}_g$ is the Scalar curvature of the manifold. We show that these conditions are optimal by constructing examples of blowing-up solutions, with arbitrarily large energy, in the case of the round sphere with a constant potential function h.