The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later i...The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later improved through its modification h^(+).However,the dual Cheeger problem and its modification themselves are relatively unexplored,especially the lack of effective approximate algorithms.To this end,we first derive equivalent spectral formulations of h^(+)and h^(+)within the framework of the nonlinear spectral theory of signless 1-Laplacian,present their interactions with the Laplacian matrix and 1-Laplacians,and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved.We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector,and provide the approximate values of h^(+)and h^(+)on the G-set for the first time.The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating it into the inverse power algorithms,leading to significantly improved approximate values on the G-set.Finally,we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework cannot be improved beyond 0.769.展开更多
This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend （CD） framework f...This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend （CD） framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power （IP） method and the steepest descent （SD） method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.展开更多
The authors establish a Cheeger-Müller type theorem for the complex valued analytic torsion introduced by Burghelea and Hailer for fiat vector bundles carrying nondegenerate symmetric bilinear forms. As a consequ...The authors establish a Cheeger-Müller type theorem for the complex valued analytic torsion introduced by Burghelea and Hailer for fiat vector bundles carrying nondegenerate symmetric bilinear forms. As a consequence, they prove the Burghelea-Haller conjecture in full generality, which gives an analytic interpretation of （the square of） the Turaev torsion.展开更多
The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data.This is an NP-hard problem that can be relaxed in the spectral graph theory,where the optimal cuts of a graph are ...The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data.This is an NP-hard problem that can be relaxed in the spectral graph theory,where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian.In this paper,we first give new notations to describe the paths,among critical eigenvectors of the graph 1-Laplacian,realizing sets with prescribed genus.We introduce the pseudo-orthogonality to characterize m_(3)(G),a special eigenvalue for the graph 1-Laplacian.Furthermore,we use it to give an upper bound for the third graph Cheeger constant h_(3)(G),that is,h_(3)(G)≤m_(3)(G).This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k−1 Cheeger constants.Eventually,we apply these results to give a method and a numerical algorithm to compute m3(G),based on a generalized inverse power method.展开更多
The Cheeger’s inequalities and some existence criteria for spectral gap and for general symmetric forms are established. The criteria are also extended to general reversible Markov processes but not reported here. Ev...The Cheeger’s inequalities and some existence criteria for spectral gap and for general symmetric forms are established. The criteria are also extended to general reversible Markov processes but not reported here. Even though in the past several decades, the topics have been widely studied, as far as we know the first problem in the unbounded case and the second one in the general case remain open.展开更多
The paper quotes the concept of Ricci curvature decay to zero. Base on this new concept, by modifying the proof of the canonical Cheeger-Gromoll Splitting Theorem, the paper proves that for a complete non-compact Riem...The paper quotes the concept of Ricci curvature decay to zero. Base on this new concept, by modifying the proof of the canonical Cheeger-Gromoll Splitting Theorem, the paper proves that for a complete non-compact Riemannian manifold M with Ricci curvature decay to zero, if there is a line in M, then the isometrically splitting M = R × N is true.展开更多
In this paper,we investigate the Sobolev spaces W^(1,p)(V)and W_(0)^(1,p)(V)on a locally finite graph G=(V,E),which are fundamental tools when we apply the variational methods to partial differential equations on grap...In this paper,we investigate the Sobolev spaces W^(1,p)(V)and W_(0)^(1,p)(V)on a locally finite graph G=(V,E),which are fundamental tools when we apply the variational methods to partial differential equations on graphs.As a key contribution of this note,we show that in general,W^(1,p)(V)≠W_(0)^(1,p)(V)on locally finite graphs,which is different from the situation on Euclidean space RN.展开更多
Ⅰ. INTRODUCTIONSuppose Ω is a convex domain with piecewise smooth boundary on a 2-dimensional sphere with radius R. Let λ<sub>1</sub>（Ω）be the first eigenvalue of the Laplacian with
The authors show that the 2-non-negative traceless bisectional curvature is preserved along the Kahler-Ricci flow. The positivity of Ricci curvature is also preserved along the Kahler-Ricci flow with 2-non-negative tr...The authors show that the 2-non-negative traceless bisectional curvature is preserved along the Kahler-Ricci flow. The positivity of Ricci curvature is also preserved along the Kahler-Ricci flow with 2-non-negative traceless bisectional curvature. As a corol- lary, the Kahler-Ricci flow with 2-non-negative traceless bisectional curvature will converge to a Kahler-Ricci soliton in the sense of Cheeger-Cromov-Hausdorff topology if complex dimension n ≥ 3.展开更多
基金supported by the National Key R&D Program of China(No.2022YFA 1005102)National Natural Science Foundation of China(Grant Nos.12401443,12325112 and 12288101).
文摘The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later improved through its modification h^(+).However,the dual Cheeger problem and its modification themselves are relatively unexplored,especially the lack of effective approximate algorithms.To this end,we first derive equivalent spectral formulations of h^(+)and h^(+)within the framework of the nonlinear spectral theory of signless 1-Laplacian,present their interactions with the Laplacian matrix and 1-Laplacians,and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved.We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector,and provide the approximate values of h^(+)and h^(+)on the G-set for the first time.The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating it into the inverse power algorithms,leading to significantly improved approximate values on the G-set.Finally,we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework cannot be improved beyond 0.769.
文摘This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend （CD） framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power （IP） method and the steepest descent （SD） method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.
基金the Qiushi Foundationthe National Natural Science Foundation of China (Nos.10571088,10621101)
文摘The authors establish a Cheeger-Müller type theorem for the complex valued analytic torsion introduced by Burghelea and Hailer for fiat vector bundles carrying nondegenerate symmetric bilinear forms. As a consequence, they prove the Burghelea-Haller conjecture in full generality, which gives an analytic interpretation of （the square of） the Turaev torsion.
基金supported by the MiUR-Dipartimenti di Eccellenza 2018–2022 grant“Sistemi distribuiti intelligenti”of Dipartimento di Ingegneria Elettrica e dell’Informazione“M.Scarano”,by the MiSE-FSC 2014–2020 grant“SUMMa:Smart Urban Mobility Management”,and by GNAMPA of INdAM.The authors would also like to thank D.A.La Manna and V.Mottola for the helpful conversations during the starting stage of this work.
文摘The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data.This is an NP-hard problem that can be relaxed in the spectral graph theory,where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian.In this paper,we first give new notations to describe the paths,among critical eigenvectors of the graph 1-Laplacian,realizing sets with prescribed genus.We introduce the pseudo-orthogonality to characterize m_(3)(G),a special eigenvalue for the graph 1-Laplacian.Furthermore,we use it to give an upper bound for the third graph Cheeger constant h_(3)(G),that is,h_(3)(G)≤m_(3)(G).This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k−1 Cheeger constants.Eventually,we apply these results to give a method and a numerical algorithm to compute m3(G),based on a generalized inverse power method.
文摘The Cheeger’s inequalities and some existence criteria for spectral gap and for general symmetric forms are established. The criteria are also extended to general reversible Markov processes but not reported here. Even though in the past several decades, the topics have been widely studied, as far as we know the first problem in the unbounded case and the second one in the general case remain open.
文摘The paper quotes the concept of Ricci curvature decay to zero. Base on this new concept, by modifying the proof of the canonical Cheeger-Gromoll Splitting Theorem, the paper proves that for a complete non-compact Riemannian manifold M with Ricci curvature decay to zero, if there is a line in M, then the isometrically splitting M = R × N is true.
基金supported by the National Key R and D Program of China(2020YFA0713100)the National Natural Science Foundation of China(12271039)the Open Project Program(K202303)of Key Laboratory of Mathematics and Complex Systems,Beijing Normal University。
文摘In this paper,we investigate the Sobolev spaces W^(1,p)(V)and W_(0)^(1,p)(V)on a locally finite graph G=(V,E),which are fundamental tools when we apply the variational methods to partial differential equations on graphs.As a key contribution of this note,we show that in general,W^(1,p)(V)≠W_(0)^(1,p)(V)on locally finite graphs,which is different from the situation on Euclidean space RN.
基金Project supported by the National Natural Science Foundation of China.
文摘Ⅰ. INTRODUCTIONSuppose Ω is a convex domain with piecewise smooth boundary on a 2-dimensional sphere with radius R. Let λ<sub>1</sub>（Ω）be the first eigenvalue of the Laplacian with
基金the National Science Foundation (No. DMS-0406346)
文摘The authors show that the 2-non-negative traceless bisectional curvature is preserved along the Kahler-Ricci flow. The positivity of Ricci curvature is also preserved along the Kahler-Ricci flow with 2-non-negative traceless bisectional curvature. As a corol- lary, the Kahler-Ricci flow with 2-non-negative traceless bisectional curvature will converge to a Kahler-Ricci soliton in the sense of Cheeger-Cromov-Hausdorff topology if complex dimension n ≥ 3.
