A note on sublinear separators and expansion

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

A note on sublinear separators and expansion

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A note on sublinear separators and expansion

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

93

Číslo periodika v rámci svazku

march 2021

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

7

Strana od-do

103273

Kód UT WoS článku

000607517300012

EID výsledku v databázi Scopus

—