Entropy of tournament digraphs

DOI10.1016/J.LAA.2019.09.026MaRDI QIDQ2332443zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 4 November 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

Shannon entropyLaplacianspectral theorytournamentsRényi entropy

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Coding theorems (Shannon theory) (94A24) Random walks on graphs (05C81)

Abstract: The R'{e}nyi $alpha$-entropy $H_{alpha}$ of complete antisymmetric directed graphs (i.e., tournaments) is explored. We optimize $H_{alpha}$ when $alpha=2$ and $3$, and find that as $alpha$ increases $H_{alpha}$'s sensitivity to what we refer to as `regularity' increases as well. A regular tournament on $n$ vertices is one with each vertex having out-degree $fracn-12$, but there is a lot of diversity in terms of structure among the regular tournaments; for example, a regular tournament may be such that each vertex's out-set induces a regular tournament (a doubly-regular tournament) or a transitive tournament (a rotational tournament). As $alpha$ increases, on the set of regular tournaments, $H_{alpha}$ has maximum value on doubly regular tournaments and minimum value on rotational tournaments. The more `regular', the higher the entropy. We show, however, that $H_2$ and $H_3$ are maximized, among all tournaments on any number of vertices by any regular tournament. We also provide a calculation that is equivalent to the von Neumann entropy, but may be applied to any directed or undirected graph and shows that the von Neumann entropy is a measure of how quickly a random walk on the graph or directed graph settles.

Recommendations

• Rényi ordering of tournaments
• Note on von Neumann and Rényi entropies of a graph
• A note on the von Neumann entropy of random graphs
• Proof of an entropy conjecture of Leighton and Moitra
• Symmetric Laplacians, quantum density matrices and their von-Neumann entropy

Cites work

• scientific article; zbMATH DE number 3173999 (Why is no real title available?)
• A history of graph entropy measures
• Interpreting the von Neumann entropy of graph Laplacians, and coentropic graphs
• Mathematical foundations of quantum mechanics. Edited by Nicholas A. Wheeler. Translated from the German by Robert T. Beyer
• Note on von Neumann and Rényi entropies of a graph
• On the number of 4-cycles in a tournament
• Quantum computation and quantum information. 10th anniversary edition
• The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states
• The on-line encyclopedia of integer sequences

Cited in

(1)

• Rényi ordering of tournaments

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Entropy of tournament digraphs

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