Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00005515" target="_blank" >RIV/00216208:11320/06:00005515 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality

Original language description

We prove that there exists a constant $k$ such that for every $n geq 1$ there exists a directed core graph $H_n$ with at least $2^n$ vertices such that a directed graph $G$ is $H_n$-colorable if and only if every subgraph of $G$ with at most $knlog(n)$vertices is $H_n$-colorable. Our examples show that in general the 'duals of relational structures' in the sense of [J. Nesetril and C. Tardif, J. Combin. Theory Ser. B, 80 (2000), pp. 80-97] can have superpolynomial size. The construction given in thispaper gives a double exponential upper bound for such a construction. Here we improve this to an exponential upper bound.

Czech name

Krátké odpovědi na exponenciálně dlouhé otázky: extremální aspekty homomorfismové duality

Czech description

Dokazujeme, že existuje konstanta k taková, že pro každé $n geq 1$ existuje orientovaný core graf $H_n$ s alespoň $2^n$ vrcholy takový, že orientovaný graf $G$ je $H_n$-obarvitelný pravě když každý podgraf $G$ s nejvýše $knlog(n)$ vrcholy je $H_n$ obarvitelný. Naše příklady ukazují, že 'duály relačních struktur' ve smyslu [J. Nešetřil a C. Tardif, J. Combin. Theory Ser. B, 80 (2000), pp. 80-97] mohou obecně mít superpolynomiální velikost. Konstrukce v tom článku dává dvojitě exponenciální horní odhadna takovou konstrukci. Zde tento odhad vylepšíme na exponenciální.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2006

Confidentiality

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

Name of the periodical

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Volume of the periodical

19

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

7

Pages from-to

914-920

UT code for WoS article

—

EID of the result in the Scopus database

—