Search

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\"owner order relations on the curves defined by the Wasserstein mean and the spectral geometric mean. We show that the near order $\preceq $ is stronger than the eigenvalue entrywise order, and that $A\natural_t B \preceq 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 L\"owner order properties of the Wasserstein mean and the spectral geometric mean are also explored., Comment: 17 pages

A $K_r$-factor of a graph $G$ is a collection of vertex disjoint $r$-cliques covering $V(G)$. We prove the following algorithmic version of the classical Hajnal--Szemer\'edi Theorem in graph theory, when $r$ is considered as a constant. 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 \texttt{NP-C}. We indeed establish characterization theorems for this problem, showing that the existence of a $K_r$-factor is equivalent to the existence of certain class of $K_r$-tilings of size $o(n)$, whose existence can be searched by the color-coding technique developed by Alon--Yuster--Zwick., Comment: 31 pages

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., Comment: 18 pages

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$. In particular, we prove that for large $n$, this probability for trees is upper bounded by the corresponding probability for a path graph. Given a minimum degree condition, we also prove a conjecture of Boyer et.\ al.\ regarding the number of zero forcing sets of a given size that a graph can have., Comment: 22 pages, 5 figures

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., Comment: 15 pages

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 $1\le \ell 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., Comment: v1 is the conference version; v2 is the journal version

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., Comment: 20 pages; 2 figures

Let $Y_{3,2}$ be the $3$-uniform hypergraph with two edges intersecting in two vertices. Our main result is that any $n$-vertex 3-uniform hypergraph with at least $\binom{n}{3} - \binom{n-m+1}{3} + o(n^3)$ edges contains a collection of $m$ vertex-disjoint copies of $Y_{3,2}$, for $m\le n/7$. The bound on the number of edges is asymptotically best possible. This problem generalizes the Matching Conjecture of Erd\H{o}s. We then use this result combined with the absorbing method to determine the asymptotically best possible minimum $(k-3)$-degree threshold for $\ell$-Hamiltonicity in $k$-graphs, where $k\ge 7$ is odd and $\ell=(k-1)/2$. Moreover, we give related results on $ Y_{k,b} $-tilings and Hamilton $ \ell $-cycles with $ d $-degree for some other values of $ k,\ell,d $., Comment: arXiv admin note: text overlap with arXiv:0903.2867 by other authors

In this paper, 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., Comment: 11 pages; the final version is published in Journal of Lie Theory

In this paper, we study the metric geometric mean introduced by Pusz and Woronowicz and the spectral geometric mean introduced by Fiedler and Pt\'ak, 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., Comment: 14 pages, 2 figures, latest revision on Aug 28, 2021

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 n2$ have a tight Hamilton cycle. This solves a conjecture of Aigner-Horev and Levy., Comment: 8 pages