Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Dimension and representations of partially ordered sets: computational complexity, bounds and structural properties

2015/18/E/ST6/00299

Keywords:

partially ordered sets dimension sparse classes of graphs

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • 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 Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Piotr Micek 

Number of co-investigators in the project: 4

Call: SONATA BIS 5 - announced on 2015-06-15

Amount awarded: 537 600 PLN

Project start date (Y-m-d): 2016-04-12

Project end date (Y-m-d): 2020-10-11

Project duration:: 54 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 (12)
  • Articles in post-conference publications (4)
  1. Boolean dimension and tree-width
    Authors:
    Stefan Felsner, Tamás Mészáros, Piotr Micek
    Academic press:
    Combinatorica (rok: 2020, tom: 40, strony: 655–677), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00493-020-4000-9 - link to the publication
  2. Nowhere dense graph classes and dimension
    Authors:
    Gwenaël Joret, Patrice Ossona de Mendez, Piotr Micek, Veit Wiechert
    Academic press:
    Combinatorica (rok: 2019, tom: 39, strony: 1055-1079), Wydawca: Springer Heidelberg
    Status:
    Published
    DOI:
    10.1007/s00493-019-3892-8 - link to the publication
  3. On an Extremal Problem for Poset Dimension
    Authors:
    Grzegorz Guśpiel, Piotr Micek, Adam Polak
    Academic press:
    Order (rok: 2018, tom: 35, strony: 489-493), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s11083-017-9444-1 - link to the publication
  4. A note on the minimum number of edges in hypergraphs with property O
    Authors:
    Gal Kronenberg, Christopher Kusch, Ander Lamaison, Piotr Micek, Tuan Tran
    Academic press:
    European Journal of Combinatorics (rok: 2019, tom: 81, strony: 172--177), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ejc.2019.05.002 - link to the publication
  5. Burling Graphs, Chromatic Number, and Orthogonal Tree-Decompositions
    Authors:
    Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert
    Academic press:
    Electronic Journal of Combinatorics (rok: 2018, tom: 25 (1), strony: -), Wydawca: Electronic Journal of Combinatorics
    Status:
    Published
    DOI:
    10.37236/7052 - link to the publication
  6. Planar Posets Have Dimension at Most Linear in Their Height
    Authors:
    Gwenaël Joret, Piotr Micek, Veit Wiechert
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2017, tom: 31 (4), strony: 2754--2790), Wydawca: SIAM PUBLICATIONS
    Status:
    Published
    DOI:
    10.1137/17M111300X - link to the publication
  7. Seymour's conjecture on 2-connected graphs of large pathwidth
    Authors:
    Tony Huynh, Gwenaël Joret, Piotr Micek, David Wood
    Academic press:
    Combinatorica (rok: 2020, tom: 40, strony: 839-868), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00493-020-3941-3 - link to the publication
  8. The dimension of posets with planar cover graphs excluding two long incomparable chains
    Authors:
    David M. Howard, Noah Streib, William T. Trotter, Bartosz Walczak, Ruidong Wang
    Academic press:
    Journal of Combinatorial Theory, Series A (rok: 2019, tom: 164, strony: 45314), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcta.2018.11.016 - link to the publication
  9. Boolean Dimension, Components and Blocks
    Authors:
    Tamás Mészáros, Piotr Micek, William T. Trotter
    Academic press:
    Order (rok: 2020, tom: 37, strony: 287-298), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s11083-019-09505-3 - link to the publication
  10. Planar Graphs Have Bounded Queue-Number
    Authors:
    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood
    Academic press:
    Journal of the ACM (rok: 2020, tom: 67, strony: 38), Wydawca: Association for Computing Machinery
    Status:
    Published
    DOI:
    10.1145/3385731 - link to the publication
  11. Sparsity and dimension
    Authors:
    Gwenaël Joret, Piotr Micek, Veit Wiechert
    Academic press:
    Combinatorica (rok: 2018, tom: 38/5, strony: 1129-1148), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00493-017-3638-4 - link to the publication
  12. Excluding a ladder
    Authors:
    Tony Huynh, Gwenaël Joret, Piotr Micek, Michał T. Seweryn, Paul Wollan
    Academic press:
    Combinatorica , Wydawca: Springer Heidelberg
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  1. Planar Graphs have Bounded Queue-Number
    Authors:
    Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood
    Conference:
    2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (rok: 2019, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 43778
    Status:
    Published
  2. The queue-number of posets of bounded width or height
    Authors:
    Kolja Knauer, Piotr Micek, Torsten Ueckerdt
    Conference:
    26th International Symposium on Graph Drawing and Network Visualization (rok: 2018, ), Wydawca: Springer International Publishing
    Data:
    konferencja 26.09.2018-28.09.2018
    Status:
    Published
  3. Boolean dimension and local dimension
    Authors:
    William T. Trotter, Bartosz Walczak
    Conference:
    The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17) (rok: 2017, ), Wydawca: Elsevier
    Data:
    konferencja 28.08.2017-1.09.2017
    Status:
    Published
  4. Burling graphs, chromatic number, and orthogonal tree-decompositions
    Authors:
    Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert
    Conference:
    The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17) (rok: 2017, ), Wydawca: Elsevier
    Data:
    konferencja 28.08.2017-1.09.2017
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy