Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

The topology of solution spaces of combinatorial problems

2016/21/N/ST6/00475

Keywords:

topological combinatorics graph coloring Hedetniemi's conjecture local search

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_14: Discrete mathematics and combinatorics

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

Marcin Wrochna 

Number of co-investigators in the project: 2

Call: PRELUDIUM 11 - announced on 2016-03-15

Amount awarded: 55 200 PLN

Project start date (Y-m-d): 2017-02-10

Project end date (Y-m-d): 2019-02-09

Project duration:: 24 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Information in the final report

  • Publication in academic press/journals (3)
  1. On inverse powers of graphs and topological implications of Hedetniemi's conjecture
    Authors:
    Marcin Wrochna
    Academic press:
    Journal of Combinatorial Theory, Series B (rok: 2019, tom: 139, strony: 267-295), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jctb.2019.02.008 - link to the publication
  2. Hedetniemi's conjecture and strongly multiplicative graphs
    Authors:
    Claude Tardif, Marcin Wrochna
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2019, tom: 33(4), strony: 2218–2250), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/19M1245013 - link to the publication
  3. The step Sidorenko property and non-norming edge-transitive graphs
    Authors:
    Daniel Král', Taísa L. Martins, Péter Pál Pach, Marcin Wrochna
    Academic press:
    Journal of Combinatorial Theory, Series A (rok: 2019, tom: 162, strony: 34-54), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcta.2018.09.012 - link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy