We study a new set of duality relations between weighted,combinatoric invariants of a graph G.The dualities arise from a non-linear transform B,acting on the weight function p.We define B on a space of real-valued fun...We study a new set of duality relations between weighted,combinatoric invariants of a graph G.The dualities arise from a non-linear transform B,acting on the weight function p.We define B on a space of real-valued functions O and investigate its properties.We show that three invariants(the weighted independence number,the weighted Lovasz number,and the weighted fractional packing number)are fixed points of B^2,but the weighted Shannon capacity is not.We interpret these invariants in the study of quantum non-locality.展开更多
The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, i...The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.展开更多
This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial a...This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.展开更多
基金supported by the Templeton Religion Trust(Grant No.TRT 0159)supported by USA Army Research Office(ARO)(Grant No.W911NF1910302)。
文摘We study a new set of duality relations between weighted,combinatoric invariants of a graph G.The dualities arise from a non-linear transform B,acting on the weight function p.We define B on a space of real-valued functions O and investigate its properties.We show that three invariants(the weighted independence number,the weighted Lovasz number,and the weighted fractional packing number)are fixed points of B^2,but the weighted Shannon capacity is not.We interpret these invariants in the study of quantum non-locality.
文摘The possibility of developing a complete graph invariant computable in polynomial time remains an open question. Consequently, creating efficient algorithms to verify non-isomorphism, including heuristic approaches, is essential. Effective implementation of these heuristics necessitates both the adaptation of existing graph invariants and the invention of novel ones, which continues to be a relevant challenge. Numerous current invariants are capable of distinguishing a significant number of graphs rapidly in real-time scenarios. In this study, we present an invariant tailored for tournaments, a specific class of directed graphs. Tournaments are particularly intriguing because the count of distinct tournaments for a given number of vertices aligns with that of undirected graphs of the same size. The introduced invariant evaluates all possible tournament subsets derived from the original digraph that share the identical arc set. For each subset tournament, standard rankings are computed and aggregated to produce the final vertex scores, which serve as the new invariant. Our analysis indicates that this newly proposed invariant diverges from the most straightforward tournament invariant, which typically assigns scores to each participant. Preliminary computational tests demonstrate that the minimal correlation between the sequences generated by these two invariants occurs at a vertex count of 15.
文摘This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.
