The homomorphism domination exponent

DOI10.1016/J.EJC.2011.03.009zbMATH Open1229.05211arXiv1004.2485OpenAlexW2062088877MaRDI QIDQ648968FDOQ648968

Authors: Swastik Kopparty, Benjamin Rossman 

Publication date: 29 November 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)| geq |Hom(G,T)|^c for every graph T. The problem of determining whether HDE(F,G) geq 1 is known as the homomorphism domination problem and its decidability is an important open question arising in the theory of relational databases. We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of graphs F and G for which HDE(F,G) is computable. In particular, we present a linear program computing HDE(F,G) in the special case where F is chordal and G is series-parallel.

Full work available at URL: https://arxiv.org/abs/1004.2485

Recommendations

• New Plain-Exponential Time Classes for Graph Homomorphism
• Lower bounds for the graph homomorphism problem
• New plain-exponential time classes for graph homomorphism
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of counting homomorphisms seen from the other side

zbMATH Keywords

relational databaseshomomorphism domination problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Database theory (68P15)

Cites Work

• Counting graph homomorphisms
• Title not available (Why is that?)
• Flag algebras
• An entropy approach to the hard-core model on bipartite graphs
• Hypergraphs, entropy, and inequalities
• On weighted graph homomorphisms
• On a problem of K. Zarankiewicz
• Title not available (Why is that?)
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the number of copies of one hypergraph in another

Cited In (9)

• Graphical Conjunctive Queries.
• Undecidability of linear inequalities in graph homomorphism densities
• Finite reflection groups and graph norms
• On some graph densities in locally dense graphs
• A new proof of the Erdős-Simonovits conjecture on walks
• A path forward: tropicalization in extremal combinatorics
• Off-diagonal commonality of graphs via entropy
• Threshold graphs maximise homomorphism densities
• Graph homomorphisms between trees

Uses Software

• ITIP

This page was built for publication: The homomorphism domination exponent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648968)