Positive graphs

DOI10.1016/J.EJC.2015.07.007MaRDI QIDQ5899554zbMATH OpenOpenAlexFDO

Authors Omar Antolín Camarena, Endre Csóka, Tamás Hubai, Gabor Lippner, László Lovász

Publication date 11 December 2015

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

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

zbMATH Keywords

edge-weighted graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We study "positive" graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edgeweights may be negative). We conjecture that all positive graphs can be obtained by taking two copies of an arbitrary simple graph and gluing them together along an independent set of nodes. We prove the conjecture for various classes of graphs including all trees. We prove a number of properties of positive graphs, including the fact that they have a homomorphic image which has at least half the original number of nodes but in which every edge has an even number of pre-images. The results, combined with a computer program, imply that the conjecture is true for all graphs up to 9 nodes.

Recommendations

• Positive graphs
• Edge-reflection positivity and weighted graph homomorphisms
• On positive hypergraphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• scientific article; zbMATH DE number 5720912

Cites work

• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Graph norms and Sidorenko's conjecture
• Large networks and graph limits
• Limits of dense graph sequences

Cited in

(12)

• Finite reflection groups and graph norms
• Impartial digraphs
• On positive hypergraphs
• Positive Fork Graph Calculus
• Positive graphs
• Locally common graphs
• On graph norms for complex‐valued functions
• Graphs with positive spectrum
• Extended commonality of paths and cycles via Schur convexity
• Domination inequalities and dominating graphs
• Disconnected common graphs via supersaturation
• Graph-codes: questions, results and methods

This page was built for publication: Positive graphs

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