Search

Let $p,q$ be two integers with $p\geq q$. Given a finite graph $F$ with no isolated vertices, the generalized Ramsey achievement game of $F$ on the complete graph $K_n$, denoted by $(p,q;K_n,F,+)$, is played by two players called Alice and Bob. In each round, Alice firstly chooses $p$ uncolored edges $e_1,e_2,...,e_p$ and colors it blue, then Bob chooses $q$ uncolored edge $f_1,f_2,...,f_q$ and colors it red; the player who can first complete the formation of $F$ in his (or her) color is the winner. The generalized achievement number of $F$, denoted by ${a}(p,q;F)$ is defined to be the smallest $n$ for which Alice has a winning strategy. If $p=q=1$, then it is denoted by ${a}(F)$, which is the classical achievement number of $F$ introduced by Harary in 1982. If Alice aims to form a blue $F$, and the goal of Bob is to try to stop him, this kind of game is called the first player game by Bollob\'{a}s. Let ${a}^*(F)$ be the smallest positive integer $n$ for which Alice has a winning strategy in the first player game. A conjecture due to Harary states that the minimum value of ${a}(T)$ is realized when $T$ is a path and the maximum value of ${a}(T)$ is realized when $T$ is a star among all trees $T$ of order $n$. He also asked which graphs $F$ satisfy $a^*(F)=a(F)$? In this paper, we proved that $n\leq {a}(p,q;T)\leq n+q\left\lfloor (n-2)/p \right\rfloor$ for all trees $T$ of order $n$, and obtained a lower bound of ${a}(p,q;K_{1,n-1})$, where $K_{1,n-1}$ is a star. We proved that the minimum value of ${a}(T)$ is realized when $T$ is a path which gives a positive solution to the first part of Harary's conjecture, and ${a}(T)\leq 2n-2$ for all trees of order $n$. We also proved that for $n\geq 3$, we have $2n-2-\sqrt{(4n-8)\ln (4n-4)}\leq a(K_{1,n-1})\leq 2n-2$ with the help of a theorem of Alon, Krivelevich, Spencer and Szab\'o. We proved that $a^*(P_n)=a(P_n)$ for a path $P_n$., Comment: 13 pages

Given a graph $T$ and a family of graphs $\mathcal{F}$, the maximum number of copies of $T$ in an $\mathcal{F}$-free graph on $n$ vertices is called the generalized Tur\'{a}n number, denoted by $ex(n, T , \mathcal{F})$. When $T= K_2$, it reduces to the classical Tur\'{a}n number $ex(n, \mathcal{F})$. Let $ex_{bip}(b,n, T , \mathcal{F})$ be the maximum number of copies of $T$ in an $\mathcal{F}$-free bipartite graph with two parts of sizes $b$ and $n$, respectively. Let $P_k$ be the path on $k$ vertices, $\mathcal{C}_{\ge k}$ be the family of all cycles with length at least $k$ and $M_k$ be a matching with $k$ edges. In this article, we determine $ex_{bip}(b,n, K_{s,t}, \mathcal{C}_{\ge 2n-2k})$ exactly in a connected bipartite graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, for $b\ge n\ge 2k+2r$ and $k\in \mathbb{Z}$, which generalizes a theorem of Moon and Moser, a theorem of Jackson and gives an affirmative evidence supporting a conjecture of Adamus and Adamus. As corollaries of our main result, we determine $ex_{bip}(b,n, K_{s,t}, P_{2n-2k})$ and $ex_{bip}(b,n, K_{s,t}, M_{n-k})$ exactly in a connected bipartite graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, which generalizes a theorem of Wang. Moreover, we determine $ex(n, K_{s,t}, \mathcal{C}_{\ge k})$ and $ex(n, K_{s,t}, P_{k})$ respectively in a connected graph $G$ with minimum degree $\delta(G) \geq r\ge 1$, which generalizes a theorem of Lu, Yuan and Zhang., Comment: 19 pages

Great progress has been made in quantum computing in recent years, providing opportunities to overcome computation resource poverty in many scientific computations like computational fluid dynamics (CFD). In this work, efforts are made to exploit quantum potentialities in CFD, and a hybrid classical and quantum computing CFD framework is proposed to release the power of current quantum computing. In this framework, the traditional CFD solvers are coupled with quantum linear algebra libraries in weak form to achieve collaborative computation between classical and quantum computing. The quantum linear solver provides high-precision solutions and scalable problem sizes for linear systems and is designed to be easily callable for solving linear algebra systems similar to classical linear libraries, thus enabling seamless integration into existing CFD solvers. Some typical cases are performed to validate the feasibility of the proposed framework and the correctness of quantum linear algorithms in CFD., Comment: 18 pages, 16 figures

Inspired by the recent discovery of a violation of strong cosmic censorship (SCC) for the near-extremal Reissner-Nordstr\"om black holes in de Sitter space (RN-dS), we investigate if the weak cosmic censorship conjecture (WCCC) can also be violated in RN-dS with a fixed cosmological constant. Our method is based on the recent formulation of examining WCCC by requiring the second law to hold, which requires the sum of areas of the event and cosmic horizons cannot decrease during the infall process of Wald's gedanken experiment. We find that the WCCC can be violated for the near-extremal RN-dS in some regimes of second-order perturbation of field configurations. Given the charge parameter of RN-dS, we can find the lowest value of the sub-extremality parameter, beyond which the WCCC holds. Our results imply that violations of SCC and WCCC could be correlated. Because of a lack of an unambiguous relation between the gravitational mass and matter's kinematic mass in asymptotically de Sitter space, we cannot compare the corresponding regimes of parameter space for the violations of SCC and WCCC. We also discuss the subtlety in formulating both the first-law and second-law approaches to examine WCCC., Comment: 12 pages, 6 figures

Let $G$ be a graph on $n$ vertices with degree sequence $(d_1,d_2......d_n)$. For a real $p \geq 1$, let $D_p(G)=\sum_{i=1}^nd_i^p$. A Tur\'an-type problem of degree power sum was initiated by Caro and Yuster \cite{caro2000degpower}: determining the function $D_p(n,H) :=\max \{D_p(G): \text{$G$ is an $n$-vertex $H$-free graph}\}$. They obtained some exact values for certain graphs $H$. For a path $P_k$, they mentioned that ``a close examination of the proof of Theorem 1.2 shows that the value of $n_0(k)$ in the statement of the theorem is $O(k^2)$", namely, they could show the $n$-vertex $P_k$-free graph with maximum degree power sum is $W_{n,k-1,\lfloor \frac{k}{2} \rfloor -1} = K_{\lfloor \frac{k}{2} \rfloor -1} \vee \left((n - \lceil \frac{k}{2} \rceil)K_1 \cup K_{1+k-2\lfloor \frac{k}{2} \rfloor} \right)$ when $n \geq c k^2$ for some constant $c$. In this note, we improve their result to a linear size of $k$ by a different approach. The bound is tight up to a constant factor., Comment: 6 pages

In 2002, Nikiforov proved that for an $n$-vertex graph $G$ with clique number $\omega$ and edge number $m$, the spectral radius $\lambda(G)$ satisfies $\lambda (G) \leq \sqrt{2(1 - 1/\omega) m}$, which confirmed a conjecture implicitly suggested by Edwards and Elphick. In this paper, we prove a local version of spectral Tur\'an inequality, which states that $\lambda^2(G)\leq 2\sum_{e\in E(G)}\frac{c(e)-1}{c(e)}$, where $c(e)$ is the order of the largest clique containing the edge $e$ in $G$. We also characterize the extremal graphs. We prove that our theorem implies Nikiforov's theorem and give an example to show that the difference of Nikiforov's bound and ours is $\Omega (\sqrt{m})$ for some cases. Additionally, we establish a spectral counterpart to Ore's problem (1962) which asks for the maximum size of an $n$-vertex graph such that its complement is connected and does not contain $F$ as a subgraph. Our result leads to a new spectral Tur\'an inequality applicable to graphs with connected complements. Finally, we disprove a conjecture of Gregory, asserting that for a connected $n$-vertex graph $G$ with chromatic number $k\geq 2$ and an independent set $S$, we have \[ \sum_{v\in S} x_v^2 \leq \frac{1}{2} - \frac{k-2}{2\sqrt{(k-2)^2 + 4(k-1)(n-k+1)}}, \] where $x_v$ is the component of the Perron vector of $G$ with respect to the vertex $v$. A modified version of Gregory's conjecture is proposed., Comment: 20 pages. This is a new version of the previous paper titled "A local version of spectral Tur\'an theorem". In this version, we add more results, including a variant of spectral Tur\'an theorem and a disproof of a conjecture of Gregory

Let $G$ be a connected graph and $\mathcal{P}(G)$ a graph parameter. We say that $\mathcal{P}(G)$ is feasible if $\mathcal{P}(G)$ satisfies the following properties: (I) $\mathcal{P}(G)\leq \mathcal{P}(G_{uv})$, if $G_{uv}=G[u\to v]$ for any $u,v$, where $G_{uv}$ is the graph obtained by applying Kelmans operation from $u$ to $v$; (II) $\mathcal{P}(G) <\mathcal{P}(G+e)$ for any edge $e\notin E(G)$. Let $P_k$ be a path of order $k$, $\mathcal{C}_{\geq k}$ the set of all cycles of length at least $k$ and $M_{k+1}$ a matching containing $k+1$ independent edges. In this paper, we mainly prove the following three results: (i) Let $n\geq k\geq 5$ and let $t=\left\lfloor\frac{k-1}{2}\right\rfloor$. Let $G$ be a $2$-connected $n$-vertex $\mathcal{C}_{\geq k}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in \mathcal{G}^1_{n,k}=\{W_{n,k,s}=K_{s}\vee ((n-k+s)K_1\cup K_{k-2s}): 2\leq s\leq t\}$. (ii) Let $n\geq k\geq 4$ and let $t=\left\lfloor\frac{k}{2}\right\rfloor-1$. Let $G$ be a connected $n$-vertex $P_{k}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\in \mathcal{G}^2_{n,k}=\{W_{n,k-1,s}=K_{s}\vee ((n-k+s+1)K_1\cup K_{k-2s-1}): 1\leq s\leq t\}.$ (iii) Let $G$ be a connected $n$-vertex $M_{k+1}$-free graph with the maximum $\mathcal{P}(G)$ where $\mathcal{P}(G)$ is feasible. Then, $G\cong K_n$ when $n=2k+1$ and $G\in \mathcal{G}^3_{n,k}=\{K_s\vee ((n-2k+s-1)K_1\cup K_{2k-2s+1}):1\leq s\leq k\}$ when $n\geq 2k+2$. Directly derived from these three main results, we obtain a series of applications in Tur\'an-type problems, generalized Tur\'an-type problems, powers of graph degrees in extremal graph theory, and problems related to spectral radius, and signless Laplacian spectral radius in spectral graph theory., Comment: V2

Let $F$ be a graph and $\SPEX (n, F)$ be the class of $n$-vertex graphs which attain the maximum spectral radius and contain no $F$ as a subgraph. Let $\EX (n, F)$ be the family of $n$-vertex graphs which contain maximum number of edges and no $F$ as a subgraph. It is a fundamental problem in spectral extremal graph theory to characterize all graphs $F$ such that $\SPEX (n, F)\subseteq \EX (n, F)$ when $n$ is sufficiently large. Establishing the conjecture of Cioab\u{a}, Desai and Tait [European J. Combin., 2022], Wang, Kang, and Xue [J. Combin. Theory Ser. B, 2023] prove that: for any graph $F$ such that the graphs in $\EX (n, F)$ are Tur\'{a}n graphs plus $O(1)$ edges, $\SPEX (n, F)\subseteq \EX (n, F)$ for sufficiently large $n$. In this paper, we prove that $\SPEX (n, F)\subseteq \EX (n, F)$ for sufficiently large $n$, where $F$ is an $n$-vertex graph with no isolated vertices and $\Delta (F) \leq \sqrt{n}/40$. We also prove a signless Laplacian spectral radius version of the above theorem. These results give new contribution to the open problem mentioned above, and can be seen as spectral analogs of a theorem of Alon and Yuster [J. Combin. Theory Ser. B, 2013]. Furthermore, as immediate corollaries, we have tight spectral conditions for the existence of several classes of special graphs, including clique-factors, $k$-th power of Hamilton cycles and $k$-factors in graphs. The first special class of graphs gives a positive answer to a problem of Feng, and the second one extends a previous result of Yan et al.

Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of $20$ topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview., Comment: v3, 30 pages, 1 figure, include comments from Clive Elphick, Xiaofeng Gu, William Linz, and Dragan Stevanovi\'c, respectively. Thanks! This paper will be published in Operations Research Transactions

Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $\delta^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $\delta^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $\delta^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $\delta^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Tur\'an numbers for matching numbers due to Erd\H{o}s and Gallai., Comment: 17 pages

Infalling matter may destroy a black hole and expose the naked singularity. Thus, Penrose proposed the weak cosmic censorship conjecture to avoid such a possibility. On the other hand, if the black hole is not destroyed by infalling matter, from the second law of black hole thermodynamics, the black hole entropy should increase due to the information carried by the infalling matter. In this work, we demonstrate by examples of perturbative near-extremal black holes in higher derivative gravity theories that the second law implies weak cosmic censorship. We also compare our proposal to the one developed by Sorce and Wald based on the first law of black hole thermodynamics and show that the latter fails to yield weak cosmic censorship in such cases. Finally, we give proof of our proposal for generic gravity theories., Comment: 5 + 11 pages, 1 figure; v2: accepted for PRD

Foucaud {\it et al.} recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let $G$ be a graph with vertex set $V(G)$, $M$ a subset of $V(G)$, and $e$ be an edge in $E(G)$, and let $P(M, e)$ be the set of pairs $(x,y)$ such that $d_G(x, y)\neq d_{G-e}(x, y)$ where $x\in M$ and $y\in V(G)$. $M$ is called a \emph{distance-edge-monitoring set} if every edge $e$ of $G$ is monitored by some vertex of $M$, that is, the set $P(M, e)$ is nonempty. The {\em distance-edge-monitoring number} of $G$, denoted by $\operatorname{dem}(G)$, is defined as the smallest size of distance-edge-monitoring sets of $G$. For two graphs $G,H$ of order $m,n$, respectively, in this paper we prove that $\max\{m\operatorname{dem}(H),n\operatorname{dem}(G)\} \leq\operatorname{dem}(G\,\Box \,H) \leq m\operatorname{dem}(H)+n\operatorname{dem}(G) -\operatorname{dem}(G)\operatorname{dem}(H)$, where $\Box$ is the Cartesian product operation. Moreover, we characterize the graphs attaining the upper and lower bounds and show their applications on some known networks. We also obtain the distance-edge-monitoring numbers of join, corona, cluster, and some specific networks., Comment: v2, 21 pages

Equation of state (EOS) for bcc tungsten at 300 K (or 3000 K) up to 1000 GPa (or 300 GPa) was predicted for the first time by solving the partition function via a direct integral approach (DIA) with ab initio calculations of the atoms' interactions. Compared with available experiments under static compressions up to 150 GPa (or 35 GPa) for room temperature (or 1673 K), all the calculated results are within the experimental uncertainty achieved very recently. Furthermore, the same procedure was performed to investigate the shock wave experiments on the EOS up to 400 GPa and 10000 K, and the calculated average pressure deviates the experimental measurements by only 2.0%. These facts suggest that the other calculated results of DIA for the EOS are reliable, and DIA as a universal method without any artificial parameters could be widely applied to predict EOS of various materials under various conditions., Comment: 5 figures, 14 figures

The structural phase behaviors of pure zirconium metal under compressions up to $160$ GPa at room temperature are investigated from the perspective of ensemble theory where the partition function is solved by our recently proposed method with \emph{ab initio} precision. The derived Gibbs free energy is employed as the very criterion to determine phase transitions and the calculated transition pressures of the $\alpha\rightarrow\omega\rightarrow\beta$ are $6.93$ and $24.83$ GPa respectively, the former one of which is so far the only theoretical result agreeing with multiple experimental measurements to our best knowledge. The differences between the obtained parameter-free equation of state and those from latest experiments are less than $1.5\%$ in the whole studied pressure range, and particularly, within $0.7\%$ when the applied pressure exceeds over $40$ GPa, the coincidence of which makes us support the argument that the previously observed anharmonicity-driven isostructural phase transition does not exist in the $\beta$-phase even though the thermal effects at room temperature are confirmed to be nontrivial to the phase stability by our quantitative comparisons with the results at $0$K., Comment: 9 pages, 6 figures

In this paper, we study the stability result of a well-known theorem of Bondy. We prove that for any 2-connected non-hamiltonian graph, if every vertex except for at most one vertex has degree at least $k$, then it contains a cycle of length at least $2k+2$ except for some special families of graphs. Our results imply several previous classical theorems including a deep and old result by Voss. We point out our result on stability in Bondy's theorem can directly imply a positive solution (in a slight stronger form) to the following problem: Is there a polynomial time algorithm to decide whether a 2-connected graph $G$ on $n$ vertices has a cycle of length at least $\min\{2\delta(G)+2,n\}$. This problem originally motivates the recent study on algorithmic aspects of Dirac's theorem by Fomin, Golovach, Sagunov and Simonov, although a stronger problem was solved by them by completely different methods. Our theorem can also help us to determine all extremal graphs for wheels on odd number of vertices. We also discuss the relationship between our results and some previous problems and theorems in spectral graph theory and generalized Tur\'{a}n problem., Comment: 17 pages

A path (cycle) is properly-colored if consecutive edges are of distinct colors. In 1997, Bang-Jensen and Gutin conjectured a necessary and sufficient condition for the existence of a Hamilton path in an edge-colored complete graph. This conjecture, confirmed by Feng, Giesen, Guo, Gutin, Jensen and Rafley in 2006, was laterly playing an important role in Lo's asymptotical proof of Bollob\'as-Erd\H{o}s' conjecture on properly-colored Hamilton cycles. In 1997, Yeo obtained a structural characterization of edge-colored graphs that containing no properly colored cycles. This result is a fundamental tool in the study of edge-colored graphs. In this paper, we first give a much shorter proof of the Bang-Jensen-Gutin Conjecture by two novel absorbing lemmas. We also prove a new sufficient condition for the existence of a properly-colored cycle and then deduce Yeo's theorem from this result and a closure concept in edge-colored graphs., Comment: 13 pages, 5 figures

Piecewise constant priors are routinely used in the Bayesian Cox proportional hazards model for survival analysis. Despite its popularity, large sample properties of this Bayesian method are not yet well understood. This work provides a unified theory for posterior distributions in this setting, not requiring the priors to be conjugate. We first derive contraction rate results for wide classes of histogram priors on the unknown hazard function and prove asymptotic normality of linear functionals of the posterior hazard in the form of Bernstein--von Mises theorems. Second, using recently developed multiscale techniques, we derive functional limiting results for the cumulative hazard and survival function. Frequentist coverage properties of Bayesian credible sets are investigated: we prove that certain easily computable credible bands for the survival function are optimal frequentist confidence bands. We conduct simulation studies that confirm these predictions, with an excellent behavior particularly in finite samples. Our results suggest that the Bayesian approach can provide an easy solution to obtain both the coefficients estimate and the credible bands for survival function in practice., Comment: 84 pages, 6 figures, 2 tables

It is a long-time pursuit of computations with \emph{ab initio} precision of thermal contributions to phase behaviors of condensed matters under extreme conditions. In this work, the pressure induced structural phase transitions of crystalline aluminum up to $600$ GPa at room temperature are investigated based on the criterion of Gibbs free energy derived directly from the partition function that formulated in the ensemble theory with the interatomic interactions characterized by density functional theory computations. The transition pressures of the FCC$\rightarrow$HCP$\rightarrow$BCC phase transitions are determined at $194$ and $361$ GPa, the axial ratio of the stable HCP structure is found to be equal to $1.62$ and the discontinuities in the equations of states are confirmed to be associated with $-0.67\%$ and $-0.90\%$ volume changes, which are all in an excellent agreement with the measurements by one of the recent experiments but differ from other experimental observations. Compared with the results obtained by the criterion of enthalpy at $0$K, this work further shows the nontrivial thermal impacts on the structural stability of aluminum under ultrahigh-pressure circumstances even at room temperature., Comment: 11 pages, 5 figures

For realistic crystals, the free energy strictly formulated in ensemble theory can hardly be obtained because of the difficulty in solving the high-dimension integral of the partition function, the dilemma of which makes it even a doubt if the rigorous ensemble theory is applicable to phase transitions of condensed matters. In the present work, the partition function of crystal vanadium under compression up to $320$ GPa at room temperature is solved by an approach developed very recently, and the derived equation of state is in a good agreement with all the experimental measurements, especially the latest one covering the widest pressure range up to $300$ GPa. Furthermore, the derived Gibbs free energy proves the very argument to understand most of the experiments reported in the past decade on the pressure-induced phase transition, and, especially, a novel phase transition sequence concerning three different phases observed very recently and the measured angles of two phases agree with our theoretical results excellently., Comment: 5pages, 5figures

Accurate nerve identification is critical during surgical procedures for preventing any damages to nerve tissues. Nerve injuries can lead to long-term detrimental effects for patients as well as financial overburdens. In this study, we develop a deep-learning network framework using the U-Net architecture with a Transformer block based fusion module at the bottleneck to identify nerve tissues from a multi-modal optical imaging system. By leveraging and extracting the feature maps of each modality independently and using each modalities information for cross-modal interactions, we aim to provide a solution that would further increase the effectiveness of the imaging systems for enabling the noninvasive intraoperative nerve identification.

Let $G$ be a graph and $\lambda(G)$ be the spectral radius of $G$. A previous result due to Nikiforov [Linear Algebra Appl., 2009] in spectral graph theory asserted that every graph $G$ on $m\geq 10$ edges contains a 4-cycle if $\lambda(G)>\sqrt{m}$. Define $f(m)$ to be the minimum number of copies of 4-cycles in such a graph. A consequence of a recent theorem due to Zhai et al. [European J. Combin., 2021] shows that $f(m)=\Omega(m)$. In this article, by somewhat different techniques, we prove that $f(m)=\Theta(m^2)$. We left the solution to $\lim\limits_{m\rightarrow \infty} \frac{f(m)}{m^2}$ as a problem, and also mention other ones for further study., Comment: 14 pages

Let $G$ be an edge-colored graph on $n$ vertices. The minimum color degree of $G$, denoted by $\delta^c(G)$, is defined as the minimum number of colors assigned to the edges incident to a vertex in $G$. In 2013, H. Li proved that an edge-colored graph $G$ on $n$ vertices contains a rainbow triangle if $\delta^c(G)\geq \frac{n+1}{2}$. In this paper, we obtain several estimates on the number of rainbow triangles through one given vertex in $G$. As consequences, we prove counting results for rainbow triangles in edge-colored graphs. One main theorem states that the number of rainbow triangles in $G$ is at least $\frac{1}{6}\delta^c(G)(2\delta^c(G)-n)n$, which is best possible by considering the rainbow $k$-partite Tur\'an graph, where its order is divisible by $k$. This means that there are $\Omega(n^2)$ rainbow triangles in $G$ if $\delta^c(G)\geq \frac{n+1}{2}$, and $\Omega(n^3)$ rainbow triangles in $G$ if $\delta^c(G)\geq cn$ when $c>\frac{1}{2}$. Both results are tight in sense of the order of the magnitude. We also prove a counting version of a previous theorem on rainbow triangles under a color neighborhood union condition due to Broersma et al., and an asymptotically tight color degree condition forcing a colored friendship subgraph $F_k$ (i.e., $k$ rainbow triangles sharing a common vertex)., Comment: 16 pages

Motivated by the counting results for color-critical subgraphs by Mubayi [Adv. Math., 2010], we study the phenomenon behind Mubayi's theorem from a spectral perspective and start up this problem with the fundamental case of triangles. We prove tight bounds on the number of copies of triangles in a graph with a prescribed number of vertices and edges and spectral radius. Let $n$ and $m$ be the order and size of a graph. Our results extend those of Nosal, who proved there is one triangle if the spectral radius is more than $\sqrt{m}$, and of Rademacher, who proved there are at least $\lfloor\frac{n}{2}\rfloor$ triangles if the number of edges is more than that of 2-partite Tur\'an graph. These results, together with two spectral inequalities due to Bollob\'as and Nikiforov, can be seen as a solution to the case of triangles of a problem of finding spectral versions of Mubayi's theorem. In addition, we give a short proof of the following inequality due to Bollob\'as and Nikiforov [J. Combin. Theory Ser. B, 2007]: $t(G)\geq \frac{\lambda(G)(\lambda^2(G)-m)}{3}$ and characterize the extremal graphs. Some problems are proposed in the end., Comment: 15 pages; 1 figure; 1 table

As the counterpart of classical theorems on cycles of consecutive lengths due to Bondy and Bollob\'as in spectral graph theory, Nikiforov proposed the following open problem in 2008: What is the maximum $C$ such that for all positive $\varepsilon\sqrt{\lfloor\frac{n^2}{4}\rfloor}$ contains a cycle of length $\ell$ for each integer $\ell\in[3,(C-\varepsilon)n]$. We prove that $C\geq\frac{1}{4}$ by a novel method, improving the existing bounds. Besides several novel ideas, our proof technique is partly inspirited by the recent research on Ramsey numbers of star versus large even cycles due to Allen, {\L}uczak, Polcyn and Zhang, and with aid of a powerful spectral inequality. We also derive an Erd\H{o}s-Gallai-type edge number condition for even cycles, which may be of independent interest., Comment: 6 pages, to appear in Journal of Graph Theory(2023). arXiv admin note: substantial text overlap with arXiv:2102.03855

For positive integers $n>d\geq k$, let $\phi(n,d,k)$ denote the least integer $\phi$ such that every $n$-vertex graph with at least $\phi$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, Erd\H{o}s, Faudree, Schelp and Simonovits proposed the study of the function $\phi(n,d,k)$, and conjectured that for any positive integers $n>d\geq k$, it holds that $\phi(n,d,k)\leq \lfloor\frac{k-1}{2}\rfloor\lfloor\frac{n}{d+1}\rfloor+\epsilon$, where $\epsilon=1$ if $k$ is odd and $\epsilon=2$ otherwise. In this paper we determine the values of the function $\phi(n,d,k)$ exactly. This confirms the above conjecture of Erd\H{o}s et al. for all positive integers $k\neq 4$ and in a corrected form for the case $k=4$. Our proof utilizes, among others, a lemma of Erd\H{o}s et al. \cite{EFSS89}, a theorem of Jackson \cite{J81}, and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin \cite{KLZ}, where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erd\H{o}s et al., Comment: 13 pages

Woodall proved that for a graph $G$ of order $n\geq 2k+3$ where $k\geq 0$ is an integer, if $e(G)\geq \binom{n-k-1}{2}+\binom{k+2}{2}+1$ then $G$ contains a $C_{\ell}$ for each $\ell\in [3,n-k]$. In this article, we prove a stability result of this theorem. As a byproduct, we give complete solutions to two problems in \cite{GN19}. Our second part is devoted to an open problem by Nikiforov: what is the maximum $C$ such that for all positive $\varepsilon\sqrt{\lfloor\frac{n^2}{4}\rfloor}$ contains a cycle of length $\ell$ for every $\ell\leq (C-\varepsilon)n$. We prove that $C\geq\frac{1}{4}$ by a method different from previous ones, improving the existing bounds. We also derive an Erd\H{o}s-Gallai type edge number condition for even cycles, which may be of independent interest., Comment: 13 pages

Sparse principal component analysis (SPCA) is a popular tool for dimensionality reduction in high-dimensional data. However, there is still a lack of theoretically justified Bayesian SPCA methods that can scale well computationally. One of the major challenges in Bayesian SPCA is selecting an appropriate prior for the loadings matrix, considering that principal components are mutually orthogonal. We propose a novel parameter-expanded coordinate ascent variational inference (PX-CAVI) algorithm. This algorithm utilizes a spike and slab prior, which incorporates parameter expansion to cope with the orthogonality constraint. Besides comparing to two popular SPCA approaches, we introduce the PX-EM algorithm as an EM analogue to the PX-CAVI algorithm for comparison. Through extensive numerical simulations, we demonstrate that the PX-CAVI algorithm outperforms these SPCA approaches, showcasing its superiority in terms of performance. We study the posterior contraction rate of the variational posterior, providing a novel contribution to the existing literature. The PX-CAVI algorithm is then applied to study a lung cancer gene expression dataset. The R package VBsparsePCA with an implementation of the algorithm is available on the Comprehensive R Archive Network (CRAN)., Comment: 27 pages, 5 tables, 1 figures