Critical exponents of graphs

DOI10.1016/J.JCTA.2015.11.003MaRDI QIDQ899490zbMATH OpenOpenAlexFDO

Authors Dominique Guillot, Apoorva Khare, Bala Rajaratnam

Publication date 28 December 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.04069

zbMATH Keywords

chordal graphsLoewner orderingpositive semidefinitenessentrywise positive mapsfractional Schur powersmatrices with structure of zeros

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Quadratic and bilinear forms, inner products (15A63)

Abstract: The study of entrywise powers of matrices was originated by Loewner in the pursuit of the Bieberbach conjecture. Since the work of FitzGerald and Horn (1977), it is known that $A^{circalpha}:=(a_{ij}^{a}lpha)$ is positive semidefinite for every entrywise nonnegative $nimesn$ positive semidefinite matrix $A=(a_{ij})$ if and only if $alpha$ is a positive integer or $alphageqn-2$. This surprising result naturally extends the Schur product theorem, and demonstrates the existence of a sharp phase transition in preserving positivity. In this paper, we study when entrywise powers preserve positivity for matrices with structure of zeros encoded by graphs. To each graph is associated an invariant called its "critical exponent", beyond which every power preserves positivity. In our main result, we determine the critical exponents of all chordal/decomposable graphs, and relate them to the geometry of the underlying graphs. We then examine the critical exponent of important families of non-chordal graphs such as cycles and bipartite graphs. Surprisingly, large families of dense graphs have small critical exponents that do not depend on the number of vertices of the graphs.

Recommendations

• The critical exponent: a novel graph invariant
• Positivity of Hadamard powers of a few band matrices
• Complete characterization of Hadamard powers preserving Loewner positivity, monotonicity, and convexity
• The critical exponent conjecture for powers of doubly nonnegative matrices
• The critical exponent for continuous conventional powers of doubly nonnegative matrices

Cites work

• scientific article; zbMATH DE number 6096647 (Why is no real title available?)
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• A General Framework for Weighted Gene Co-Expression Network Analysis
• Algorithmic graph theory and perfect graphs
• Coalescence, majorization, edge valuations and the laplacian spectra of graphs
• Complete characterization of Hadamard powers preserving Loewner positivity, monotonicity, and convexity
• Covariance regularization by thresholding
• Extensions of band matrices with band inverses
• Fonctions opérant sur les fonctions définies-positives
• Functions Operating on Positive Definite Matrices and a Theorem of Schoenberg
• Functions preserving positive definiteness for sparse matrices
• Functions that preserve families of positive semidefinite matrices
• Hub Discovery in Partial Correlation Graphs
• Hyper Inverse Wishart Distribution for Non-decomposable Graphs and its Application to Bayesian Inference for Gaussian Graphical Models
• Large-Scale Correlation Screening
• Monotonicity for entrywise functions of matrices
• On a parametrization of positive semidefinite matrices with zeros
• On fractional Hadamard powers of positive definite matrices
• On rigid circuit graphs
• Positive definite completion problems for Bayesian networks
• Positive definite completions of partial Hermitian matrices
• Positive definite functions on spheres
• Positive definite matrices and absolutely monotonic functions
• Positive definite sequences and absolutely monotonic functions
• Positive semidefinite matrices with a given sparsity pattern
• Positivity preserving Hadamard matrix functions
• Retaining positive definiteness in thresholded matrices
• Schur products and matrix completions
• Simplicial decompositions of graphs: A survey of applications
• The Theory of Infinitely Divisible Matrices and Kernels
• The minimum rank of symmetric matrices described by a graph: a survey

Cited in

(13)

• Positivity of Hadamard powers of a few band matrices
• Positivity preservers forbidden to operate on diagonal blocks
• The critical exponent conjecture for powers of doubly nonnegative matrices
• The critical exponent: a novel graph invariant
• A panorama of positivity. II: Fixed dimension
• scientific article; zbMATH DE number 7415089 (Why is no real title available?)
• Blowup polynomials and delta-matroids of graphs
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• The critical exponent for generalized doubly nonnegative matrices
• Totally positive kernels, Pólya frequency functions, and their transforms
• Coalescence and criticality of graphs
• THE NEW UNIVERSAL ESTIMATION FOR EXPONENTS OF GRAPHS
• Critical phenomena in exponential random graphs

This page was built for publication: Critical exponents of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899490)