Asymptotically optimal induced universal graphs

DOI10.1007/s00039-017-0396-9zbMath1358.05143OpenAlexW2586156068MaRDI QIDQ521601

Noga Alon

Publication date: 11 April 2017

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00039-017-0396-9

zbMATH Keywords

induced subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (17)

Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Supertrees ⋮ Near-optimal induced universal graphs for cycles and paths ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Isomorphisms between random graphs ⋮ Unnamed Item ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ Induced Universal Hypergraphs ⋮ Universality of random permutations ⋮ Universal arrays ⋮ Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs ⋮ Right-angled Coxeter groups, universal graphs, and Eulerian polynomials ⋮ Lower bounds for superpatterns and universal sequences ⋮ Complexity and randomness in the Heisenberg groups (and beyond) ⋮ Isometric Universal Graphs ⋮ Shorter Labeling Schemes for Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced-universal graphs for graphs with bounded maximum degree
• On induced-universal graphs for the class of bounded-degree graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Graphs which contain all small graphs
• On the order of uniprimitive permutation groups
• Bipartite decomposition of random graphs
• Permutation groups, minimal degrees and quantum computing.
• Adjacency Labeling Schemes and Induced-Universal Graphs
• Universal graphs and induced-universal graphs
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• On the orders of Primitive Permutation Groups
• Implicat Representation of Graphs
• Cliques in random graphs
• Ramsey properties of orientations of graphs
• Optimal Induced Universal Graphs and Adjacency Labeling for Trees
• On minimal n-universal graphs
• Universal graphs and universal functions
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• The Maximum Order of the Group of a Tournament

This page was built for publication: Asymptotically optimal induced universal graphs