English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Twin-width is a new parameter informally measuring how diverse are theneighbourhoods of the graph vertices, and it extends also to other binaryrelational structures, e.g. to digraphs and posets. It was introduced just veryrecently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the coreresults of these authors is that FO model checking on graph classes of boundedtwin-width is in FPT. With that result, they also claimed that posets ofbounded width have bounded twin-width, thus capturing prior result on FO modelchecking of posets of bounded width in FPT. However, their translation fromposet width to twin-width was indirect and giving only a very loosedouble-exponential bound. We prove that posets of width d have twin-width atmost 9d with a direct and elegant argument, and show that this bound isasymptotically tight. Specially, for posets of width 2 we prove that in theworst case their twin-width is also equal 2. These two theoretical results arecomplemented with straightforward algorithms to construct the respectivecontraction sequence for a given poset.

Twin-Width is Linear in the Poset Width