Luyining (Elaine) Gan

We prove the following algorithmic version of the classical Hajnal-Szemer\'edi Theorem in graph theory. Given $r,c,n\in \mathbb{N}$ such that $n\in r\mathbb{N}$, let $G$ be an $n$-vertex graph with minimum degree at least $(1−1/r)n−c$. Then there is an algorithm with running time $2^{c^{O(1)}}n^{O(1)}$ that outputs either a $K_r$-factor of $G$ or a certificate showing that none exists, namely, this problem is fixed-parameter tractable in $c$. On the other hand, it is known that if $c=n^\varepsilon$ for fixed $\varepsilon\in(0,1)$, the problem is NP-C.

Given $1\le \ell < k$ and $\delta\ge0$, let $\textbf{PM}(k,\ell,\delta)$ be the decision problem for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs with minimum $\ell$-degree at least $\delta\binom{n-\ell}{k-\ell}$. For $k\ge 3$, the decision problem in general $k$-uniform hypergraphs, equivalently $\textbf{PM}(k,\ell,0)$, is one of Karp's 21 NP-complete problems. Moreover, for $k\ge 3$, a reduction of Szymańska showed that $\textbf{PM}(k, \ell, \delta)$ is NP-complete for $\delta < 1-(1-1/k)^{k-\ell}$. A breakthrough by Keevash, Knox and Mycroft resolved this problem for $\ell=k-1$ by showing that $\textbf{PM}(k, k-1, \delta)$ is in P for $\delta > 1/k$. Based on their result for $\ell=k-1$, Keevash, Knox and Mycroft conjectured that $\textbf{PM}(k, \ell, \delta)$ is in P for every $\delta > 1-(1-1/k)^{k-\ell}$.

In this paper it is shown that this decision problem for perfect matchings can be reduced to the study of the minimum $\ell$-degree condition forcing the existence of fractional perfect matchings. That is, we hopefully resolve the ``computational complexity'' aspect of the problem by reducing it to a well-known extremal problem in hypergraph theory. In particular, together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for $\ell\ge 0.4k$. Moreover, we also supply an algorithm that outputs a perfect matching, provided that one exists.

We introduce new type of quantum divergence defined by the difference of trace values between the weighted arithmetic and spectral geometric means. Several interesting properties related to such quantum divergence such as the invariance property, the in-betweenness property, and the characterization of the (s-)geodesically convex set have been established. We also show the existence and uniqueness of barycenter, minimizing the weighted sum of such quantum divergences.

On the space of positive definite matrices, several operator means are popular and have been studied extensively. In this paper, we investigate the near order and the Löwner order relations on the curves defined by the Wasserstein mean and the spectral geometric mean. We show that the near order $\prec$ is stronger than the eigenvalue entrywise order, and that $A\natural_t B \prec A\diamond_t B$ for $t \in [0,1]$. We prove the monotonicity properties of the curves originated from the Wasserstein mean and the spectral geometric mean in terms of the near order. The Loewner order properties of the Wasserstein mean and the spectral geometric mean are also explored.

Given a graph $G$ with vertices $\{v_1,\ldots,v_n\}$, we define $\mathcal{S}(G)$ to be the set of symmetric matrices $A=[a_{i,j}]$ such that for $i\ne j$ we have $a_{i,j}\ne 0$ if and only if $v_iv_j\in E(G)$. Motivated by the Graph Complement Conjecture, we say that a graph $G$ is complementary vanishing if there exist matrices $A \in \mathcal{S}(G)$ and $B \in \mathcal{S}(\overline{G})$ such that $AB=O$. We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most $8$ vertices are complementary vanishing.

Given a graph $G$ and a real number $0\le p\le 1$, we define the random set $B_p(G)\subset V(G)$ by including each vertex independently and with probability $p$. We investigate the probability that the random set $B_p(G)$ is a zero forcing set of $G$. Along the way, we prove some special cases of a conjecture of Boyer et. al. regarding the number of zero forcing sets of a given size that a graph can have.

There exist lots of distinct geometric means on the cone of positive definite Hermitian matrices such as the metric geometric mean, spectral geometric mean, log-Euclidean mean and Wasserstein mean. In this paper, we prove the log-majorization relation on the singular values of the product of given two positive definite matrices and their (metric and spectral) geometric means. We also establish the weak log-majorization between the spectra of two-variable Wasserstein mean and spectral geometric mean. In particular, we verify with certain condition on variables that two-variable Wasserstein mean converges decreasingly to the log-Euclidean mean with respect to the weak log-majorization.

For $k>b\ge 0$ such that $ n \ge (2(2k-b)^2+1)(k-1)m+m$, we show that any $ k $-graph $H$ with at least $ \binom{n}{k} - \binom{n-m+1}{k} + o(n^k) $ edges contains a $Y_{k,b}$-tiling of size $m$. %Note that $m\le\frac{n}{67}$. What is more, we show the edge condition of $Y_{3,2}$-tiling holds for any $ m\le\frac{n}{7} $. These give new results on $ d $-degree Hamilton $\ell$-cycle problem.

For all $k\ge3$, $1\leq \ell < k / 2$ and $\max\{k-\ell,\ell+1\}\le d \le k-1 $, we give an asymptotically bound on the minimum $ d $-degree for the existence of Hamilton $ \ell $-cycles in $k$-graphs, where $ k-\ell $ divides $ n $. We show that the bound is asymptotically best possible in some cases: when $d < 2\ell \le k-1$ such that $$2k-b \ge (2(2k-b-d)^2+1)(k-d-1)+1$$ or when $ k $ is odd, $ k\ge7,\ell=(k-1)/2 $ and $d=k-3$.

This chapter surveys some classical and recently discovered inequalities for matrix exponentials and their extensions to Lie groups. Some questions are asked.

In this paper, we introduce the limit, unique solution of the nonlinear equations, geodesic property, tolerance relations and pinch on the spectral geometric mean for two positive definite operators. We show that the spectral geometric mean is a geodesic with respect to some semi-metric. We also prove that the tolerance relation on determinant one matrices can be characterized by the spectral geometric mean. Moreover, two positive tuples can be pinched by the spectral geometric mean.

We establish some new properties of spectral geometric mean. In particular, we prove a log majorization relation between $$\left(B^{ts/2}A^{(1-t)s}B^{ts/2} \right)^{1/s}$$ and the $t$-spectral mean $$A\natural_t B :=(A^{-1}\sharp B)^{t}A(A^{-1}\sharp B)^{t}$$ of two positive semidefinite matrices $A$ and $B$, where $A\sharp B$ is the geometric mean, and the $t$-spectral mean is the dominant one. The limit involving $t$-spectral mean is also studied. We then extend all the results in the context of symmetric spaces of negative curvature.

Given $1\le \ell < k$ and $\delta\ge0$, let $\textbf{PM}(k,\ell,\delta)$ be the decision problem for the existence of perfect matchings in $n$-vertex $k$-uniform hypergraphs with minimum $\ell$-degree at least $\delta\binom{n-\ell}{k-\ell}$. For $k\ge 3$, the decision problem in general $k$-uniform hypergraphs, equivalently $\textbf{PM}(k,\ell,0)$, is one of Karp's 21 NP-complete problems. Moreover, for $k\ge 3$, a reduction of Szymańska showed that $\textbf{PM}(k, \ell, \delta)$ is NP-complete for $\delta < 1-(1-1/k)^{k-\ell}$. A breakthrough by Keevash, Knox and Mycroft [STOC '13] resolved this problem for $\ell=k-1$ by showing that $\textbf{PM}(k, k-1, \delta)$ is in P for $\delta > 1/k$. Based on their result for $\ell=k-1$, Keevash, Knox and Mycroft conjectured that $\textbf{PM}(k, \ell, \delta)$ is in P for every $\delta > 1-(1-1/k)^{k-\ell}$.

In this paper it is shown that this decision problem for perfect matchings can be reduced to the study of the minimum $\ell$-degree condition forcing the existence of fractional perfect matchings. That is, we hopefully solve the ``computational complexity'' aspect of the problem by reducing it to a well-known extremal problem in hypergraph theory. In particular, together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for $\ell\ge 0.4k$.

We show that for any fixed $\alpha>0$, cherry-quasirandom 3-graphs of positive density and sufficiently large order $n$ with minimum vertex degree $\alpha\binom{n}{2}$ have a tight Hamilton cycle. This solves a conjecture of Aigner-Horev and Levy.

For $n\geq 2$, let $S^*_n = \{(0,n,0),(0,n-1,1),(1,n-1,0),(n,0,0),(n-1,0,1),(n-1, 1, 0)\}$. An $n \times n$ zero-nonzero pattern A allows $S^*_n$ if $S^*_n \subset i(A)$ and requires $S^*_n$ if $S^*_n = i(A)$. The study of zero-nonzero patterns allowing $S^*_n$ was introduced by Berliner et al. In this paper, we give complete characterizations of irreducible zero-nonzero path patterns and double-star patterns that allow $S^*_n$. Moreover, all irreducible zero-nonzero tree patterns of order 5 and 6 that allow $S^*_n$ are also characterized.

In this paper, we study the metric geometric mean introduced by Pusz and Woronowicz and the spectral geometric mean introduced by Fiedler and Pták, originally for positive definite matrices. The relation between $t$-metric geometric mean and $t$-spectral geometric mean is established via log majorization. The result is then extended in the context of symmetric space associated with a noncompact semisimple Lie group. For any Hermitian matrices $X$ and $Y$, So's matrix exponential formula asserts that there are unitary matrices $U$ and $V$ such that $$e^{X/2}e^Ye^{X/2} = e^{UXU^*+VYV^*}.$$ In other words, the Hermitian matrix $\log (e^{X/2}e^Ye^{X/2})$ lies in the sum of the unitary orbits of $X$ and $Y$. So's result is also extended to a formula for adjoint orbits associated with a noncompact semisimple Lie group.

We give a simple formula for sectional curvatures on the general linear group, which is also valid for many other matrix groups. Similar formula is given for a reductive Lie group. We also discuss the relation between commuting matrices and zero sectional curvature.

In this paper, cluster synchronization in community network with nonidentical nodes is investigated. Through introducing proper adaptive strategy into impulsive control scheme, adaptive impulsive controllers are designed for achieving the cluster synchronization. In this adaptive impulsive control scheme, for any given networks, the impulsive gains can adjust themselves to proper values according to the proposed adaptive strategy when the impulsive intervals are fixed. The impulsive instants can be estimated by solving a sequence of maximum value problems when the impulsive gains are fixed. Both community networks without and with coupling delay are considered. Based on the Lyapunov function method and mathematical analysis technique, two synchronization criteria are derived. Several numerical examples are performed to verify the effectiveness of the derived theoretical results.

In this paper, cluster synchronization in community network with nonidentical nodes is investigated. By combining intermittency with a pinning control scheme, some effective controllers are designed. In the control scheme, only one node in each community is controlled and coupling weights of a spanning tree in each community are enhanced. Based on the Lyapunov function method and mathematical analysis technique, two results for achieving cluster synchronization are obtained. Noticeably, by introducing an adaptive strategy, some universal adaptive intermittent pinning controllers are designed for different networks. Finally, two numerical simulations are performed to verify the correctness of the derived results.