English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The idea of implicit representation of graphs was introduced in [S. Kannan,M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. DiscreteMathematics, 5 (1992) 596--603] and can be defined as follows. A representationof an $n$-vertex graph $G$ is said to be implicit if it assigns to each vertexof $G$ a binary code of length $O(\log n)$ so that the adjacency of twovertices is a function of their codes. Since an implicit representation of an$n$-vertex graph uses $O(n\log n)$ bits, any class of graphs admitting such arepresentation contains $2^{O(n\log n)}$ labelled graphs with $n$ vertices. Inthe terminology of [J. Balogh, B. Bollob\'{a}s, D. Weinreich, The speed ofhereditary properties of graphs, J. Combin. Theory B 79 (2000) 131--156] suchclasses have at most factorial speed of growth. In this terminology, theimplicit graph conjecture can be stated as follows: every class with at mostfactorial speed of growth which is hereditary admits an implicitrepresentation. The question of deciding whether a given hereditary class hasat most factorial speed of growth is far from being trivial. In the presentpaper, we introduce a number of tools simplifying this question. Some of themcan be used to obtain a stronger conclusion on the existence of an implicitrepresentation. We apply our tools to reveal new hereditary classes with thefactorial speed of growth. For many of them we show the existence of animplicit representation.

Implicit Representations and Factorial Properties of Graphs