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:
-
-
(Preview, Dissemination version, Version of record, pdf, 2.3MB, Terms of use)
-
Authors
Contributors
+ Zivny, S
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Oxford college:
- Jesus College
- Role:
- Supervisor
- ORCID:
- 0000-0002-0263-159X
+ Goldberg, L
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Oxford college:
- St Edmund Hall
- Role:
- Supervisor
- ORCID:
- 0000-0003-1879-6089
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- http://dx.doi.org/10.13039/501100000288
- Funding agency for:
- Focke, J
- Grant:
- EP/M508111/1
- Programme:
- UK research council doctoral training funding scheme
+ European Research Council
More from this funder
- Funding agency for:
- Goldberg, L
- Grant:
- 334828
- Programme:
- Funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007--2013)
+ European Research Council
More from this funder
- Funding agency for:
- Zivny, S
- Goldberg, L
- Focke, J
- Grant:
- 714532
- 334828
- 714532
- Programme:
- Funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
+ Royal Society
More from this funder
- Funding agency for:
- Zivny, S
- Programme:
- Royal Society University Research Fellowship
- DOI:
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
- Language:
-
English
- Keywords:
- Subjects:
- Deposit date:
-
2021-03-02
- ARK identifier:
Terms of use
- Copyright holder:
- Focke, J
- Copyright date:
- 2020
If you are the owner of this record, you can report an update to it here: Report update to this record