Critical exponents of graphs

DOI10.1016/J.JCTA.2015.11.003zbMATH Open1328.05028arXiv1504.04069OpenAlexW1861968797MaRDI QIDQ899490FDOQ899490

Apoorva Khare, Bala Rajaratnam, Dominique Guillot

Publication date: 28 December 2015

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

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.

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

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

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)

Cites Work

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

Cited In (11)

• Positivity of Hadamard powers of a few band matrices
• Positivity preservers forbidden to operate on diagonal blocks
• The critical exponent: a novel graph invariant
• A panorama of positivity. II: Fixed dimension
• Title not available (Why is that?)
• Blowup polynomials and delta-matroids of graphs
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• 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)