The log concavity of two graphical sequences

• URL: http://arxiv.org/abs/2501.03709v2
• Date: Mon, 20 Jan 2025 01:09:45 GMT
• Title: The log concavity of two graphical sequences
• Authors: Minjia Shi, Lu Wang, Patrick Sole,
• Abstract summary: We show that the series of valencies of distance regular graphs is log-concave. Consequences for strongly regular graphs, two-weight codes, and completely regular codes are derived.
• Score: 16.288333967452612
• License:
• Abstract: We show that the large Cartesian powers of any graph have log-concave valencies with respect to a ffxed vertex. We show that the series of valencies of distance regular graphs is log-concave, thus improving on a result of (Taylor, Levingston, 1978). Consequences for strongly regular graphs, two-weight codes, and completely regular codes are derived. By P-Q duality of association schemes the series of multiplicities of Q-polynomial association schemes is shown, under some assumption, to be log-concave.

Related papers

• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  We study the so-called emph$k$-core estimator, which outputs a correspondence that induces a large, common subgraph of both graphs. We specialize our general framework to derive new results on exact and partial recovery in correlated block models, correlated Chung-Lu geometric graphs, and correlated random graphs.
  arXiv  Detail & Related papers  (2023-02-10T18:21:35Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• Tensor Rank and Other Multipartite Entanglement Measures of Graph States [5.8087716340417765]
  Graph states play an important role in quantum information theory through their connection to measurement-based computing and error correction. We show that several multipartite extensions of bipartite entanglement measures are dichotomous for graph states based on the connectivity of the corresponding graph.
  arXiv  Detail & Related papers  (2022-09-13T21:59:31Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Asymptotic entropy of the Gibbs state of complex networks [68.8204255655161]
  The Gibbs state is obtained from the Laplacian, normalized Laplacian or adjacency matrices associated with a graph. We calculated the entropy of the Gibbs state for a few classes of graphs and studied their behavior with changing graph order and temperature. Our results show that the behavior of Gibbs entropy as a function of the temperature differs for a choice of real networks when compared to the random ErdHos-R'enyi graphs.
  arXiv  Detail & Related papers  (2020-03-18T18:01:28Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
  arXiv  Detail & Related papers  (2020-02-13T17:58:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.