Solution of two fractional packing problems of Lovász

A. Schrijver; P. D. Seymour

doi:10.1016/j.disc.2006.03.018

Solution of two fractional packing problems of Lovász

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

Abstract

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

Original language	English (US)
Pages (from-to)	973-978
Number of pages	6
Journal	Discrete Mathematics
Volume	306
Issue number	10-11
DOIs	https://doi.org/10.1016/j.disc.2006.03.018
State	Published - May 28 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.03.018

Cite this

@article{94ea31527dbc4aa9ab2e994b6133a0f4,

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 νk (H′) = k · ν* (H′) holds for each hypergraph H′ arising from H by multiplication of points, then νk (H) = τk (H);. (* *) if τk (H′) = k · τ* (H′) holds for each hypergraph H′ arising from H by removing edges, then τk (H) = νk (H). We prove and generalize assertion (*) and give a counterexample to (* *).",

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

year = "2006",

month = may,

day = "28",

doi = "10.1016/j.disc.2006.03.018",

language = "English (US)",

volume = "306",

pages = "973--978",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "10-11",

}

TY - JOUR

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

AU - Schrijver, A.

AU - Seymour, P. D.

PY - 2006/5/28

Y1 - 2006/5/28

N2 - Lovász asked whether the following is true for each hypergraph H and natural number k:. (*) if νk (H′) = k · ν* (H′) holds for each hypergraph H′ arising from H by multiplication of points, then νk (H) = τk (H);. (* *) if τk (H′) = k · τ* (H′) holds for each hypergraph H′ arising from H by removing edges, then τk (H) = νk (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 νk (H′) = k · ν* (H′) holds for each hypergraph H′ arising from H by multiplication of points, then νk (H) = τk (H);. (* *) if τk (H′) = k · τ* (H′) holds for each hypergraph H′ arising from H by removing edges, then τk (H) = νk (H). We prove and generalize assertion (*) and give a counterexample to (* *).

UR - http://www.scopus.com/inward/record.url?scp=33746786439&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746786439&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.03.018

DO - 10.1016/j.disc.2006.03.018

M3 - Article

AN - SCOPUS:33746786439

SN - 0012-365X

VL - 306

SP - 973

EP - 978

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10-11

ER -

Solution of two fractional packing problems of Lovász

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this