Thesis icon

Thesis

On the complexity of counting homomorphisms under surjectivity constraints

Abstract:

Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different structures in G, thereby providing a framework that captures some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homo...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
New College
Role:
Author
ORCID:
https://orcid.org/0000-0002-6895-755X

Contributors

Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Jesus College
Role:
Supervisor
ORCID:
0000-0002-0263-159X
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Edmund Hall
Role:
Supervisor
ORCID:
0000-0003-1879-6089
More from this funder
Programme:
UK research council doctoral training funding scheme
Funding agency for:
Focke, J
Grant:
EP/M508111/1
More from this funder
Programme:
Funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
Funding agency for:
Zivny, S
Goldberg, L
Focke, J
Grant:
714532
334828
714532
More from this funder
Programme:
Funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007--2013)
Funding agency for:
Goldberg, L
Grant:
334828
More from this funder
Programme:
Royal Society University Research Fellowship
Funding agency for:
Zivny, S
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP