The homomorphism domination exponent

DOI10.1016/J.EJC.2011.03.009MaRDI QIDQ648968zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty, Benjamin Rossman

Publication date 29 November 2011

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 4216032 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• An entropy approach to the hard-core model on bipartite graphs
• Counting graph homomorphisms
• Flag algebras
• Hypergraphs, entropy, and inequalities
• On a problem of K. Zarankiewicz
• On the number of copies of one hypergraph in another
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On weighted graph homomorphisms

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

Describes a project that uses

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)