Advancement: On Graph Homomorphism Counts

Speaker Name
Wei-Lin Wu
Speaker Title
Computer Science Ph.D. Student
Speaker Organization
Computer Science Ph.D.
Start Time
End Time
Location
Virtual Event

Join us on Zoomhttps://ucsc.zoom.us/j/93157393813?pwd=TnJQYit1djUxL05DRkc3STFnUnRCZz09 / Passcode: 810088

Description: A celebrated theorem by Lovasz states that graph isomorphism can be characterized by the left profile, where the left profile of a graph F is the vector that consists of the homomorphism counts from all graphs F' to F. In other words, the theorem says that two graphs G and H are isomorphic if and only if they have the same left profile. This result has motivated a line of further research on characterizing numerous equivalence relations that are relaxations of graph isomorphism (i.e., equivalence relations among graphs that are coarser than isomorphism), by restricting the left profile to certain graphs.

Various remarkable results have been obtained, including those by Dvorak and later on by Dell, Grohe and Rattan on characterizing equivalence in counting logics with a limited number of variables and indistinguishability via the k-dimensional Weisfeiler-Leman algorithm, a well-known heuristic approach to the graph isomorphism problem. In parallel to Lovasz, a theorem by Chaudhuri and Vardi asserts that graph isomorphism can also be characterized by the right profile, where the right profile of a graph F is the vector whose entries are the homomorphism counts from F to all graphs F'. Some equivalence relations among graphs, such as chromatic equivalence, can be characterized by restricting the right profile. We embarked on the investigation of which equivalence relations that are relaxations of graph isomorphism can be characterized by restricting the left or right profile, and discussing differences between the two types of restrictions. We propose to delve deeper in this line of research, aiming towards a general result for characterizing equivalence relations obtained by restricting the right profiles.

Advisor
Phokion G. Kolaitis