The entropy of random-free graphons and properties
classification
🧮 math.CO
keywords
entropyrandom-freegraphongraphgraphonsrandomsubquadraticbelongs
read the original abstract
Every graphon defines a random graph on any given number $n$ of vertices. It was known that the graphon is random-free if and only if the entropy of this random graph is subquadratic. We prove that for random-free graphons, this entropy can grow as fast as any subquadratic function. However, if the graphon belongs to the closure of a random-free graph property, then the entropy is $O(n \log n)$. We also give a simple construction of a non-stepfunction random-free graphon for which this entropy is linear, refuting a conjecture of Janson.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.