Solution of two fractional packing problems of Lovász

A. Schrijver; P.D. Seymour

doi:10.1016/0012-365X(79)90122-5

Solution of two fractional packing problems of Lovász

A. Schrijver, P.D. Seymour

Mathematics and Computer Science

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

Abstract

Lovász asked whether the following is true for each hypergraph H and natural number k: (*) if vk (H') = k · v* (H') holds for each hypergraph H' arising from H by multiplication of points, then vk(H) = tk(H); (**) if tk(H') = k · t*(H') holds for each hypergraph H' arising by removing edges, then tk (H) = vk (H). We prove and generalize assertion (*) and give a counterexample to (**).

Original language	English
Pages (from-to)	177-184
Number of pages	8
Journal	Discrete Mathematics
Volume	26
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(79)90122-5
Publication status	Published - 1979

Access to Document

10.1016/0012-365X(79)90122-5

Fingerprint Dive into the research topics of 'Solution of two fractional packing problems of Lovász'. Together they form a unique fingerprint.

Cite this

@article{d8edcf6ec55b49f9941caae88b1dff44,

title = "Solution of two fractional packing problems of Lov{\'a}sz",

abstract = "Lov{\'a}sz asked whether the following is true for each hypergraph H and natural number k: (*) if vk (H') = k · v* (H') holds for each hypergraph H' arising from H by multiplication of points, then vk(H) = tk(H); (**) if tk(H') = k · t*(H') holds for each hypergraph H' arising by removing edges, then tk (H) = vk (H). We prove and generalize assertion (*) and give a counterexample to (**).",

author = "A. Schrijver and P.D. Seymour",

year = "1979",

doi = "10.1016/0012-365X(79)90122-5",

language = "English",

volume = "26",

pages = "177--184",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Solution of two fractional packing problems of Lovász

AU - Schrijver, A.

AU - Seymour, P.D.

PY - 1979

Y1 - 1979

N2 - Lovász asked whether the following is true for each hypergraph H and natural number k: (*) if vk (H') = k · v* (H') holds for each hypergraph H' arising from H by multiplication of points, then vk(H) = tk(H); (**) if tk(H') = k · t*(H') holds for each hypergraph H' arising by removing edges, then tk (H) = vk (H). We prove and generalize assertion (*) and give a counterexample to (**).

AB - Lovász asked whether the following is true for each hypergraph H and natural number k: (*) if vk (H') = k · v* (H') holds for each hypergraph H' arising from H by multiplication of points, then vk(H) = tk(H); (**) if tk(H') = k · t*(H') holds for each hypergraph H' arising by removing edges, then tk (H) = vk (H). We prove and generalize assertion (*) and give a counterexample to (**).

U2 - 10.1016/0012-365X(79)90122-5

DO - 10.1016/0012-365X(79)90122-5

M3 - Article

VL - 26

SP - 177

EP - 184

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

ER -