A note on sublinear separators and expansion

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437036" target="_blank" >RIV/00216208:11320/21:10437036 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=avrLyTNO5R" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=avrLyTNO5R</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2020.103273" target="_blank" >10.1016/j.ejc.2020.103273</a>

Result language

angličtina

Original language name

A note on sublinear separators and expansion

Original language description

For a hereditary class g of graphs, let s(g)(n) be the minimum function such that each n-vertex graph in g has a balanced separator of order at most s(g)(n), and let del(g)(r) be the minimum function bounding the expansion of g, in the sense of bounded expansion theory of Nesetril and Ossona de Mendez. The results of Plotkin et al. (1994) and Esperet and Raymond (2018) imply that if s(g)(n) = Theta(n(1-epsilon)) for some epsilon &gt; 0, then del(g)(r) = Omega(r(1/2 epsilon-1)/polylog r) and del(g)(r) = 0(r(1/epsilon-1) polylog r). Answering a question of Esperet and Raymond, we show that neither of the exponents can be substantially improved. (C) 2020 Elsevier Ltd. All rights reserved.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Volume of the periodical

93

Issue of the periodical within the volume

march 2021

Country of publishing house

GB - UNITED KINGDOM

Number of pages

7

Pages from-to

103273

UT code for WoS article

000607517300012

EID of the result in the Scopus database

—