pith. sign in

arxiv: 1205.3529 · v1 · pith:FEU3SGSRnew · submitted 2012-05-15 · 🧮 math.CO

The entropy of random-free graphons and properties

classification 🧮 math.CO
keywords entropyrandom-freegraphongraphgraphonsrandomsubquadraticbelongs
0
0 comments X
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.