Fractal property of the graph homomorphism order

2016/06/25 by Fiala, Jiří, Hubička, Jan, Long, Yangjing +1 · 1 citation
#05C15 #05C60 #06A06 #28A80 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1606.07881

Abstract

We show that every interval in the homomorphism order of finite undirected graphs is either universal or a gap. Together with density and universality this "fractal" property contributes to the spectacular properties of the homomorphism order. We first show the fractal property by using Sparse Incomparability Lemma and then by more involved elementary argument.

Cited by

• Universality of asymptotic graph homomorphism

Related

• Gaps in full homomorphism order
• Universality of intervals of line graph order
• Phylogenetic trees and homomorphisms
• Density and Fractal Property of the Class of Oriented Trees
• Combinatorial Properties of Finite Models