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

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

2 Scopus citations

Abstract

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

Original language	English (US)
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
State	Published - 1979
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

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

Cite this

@article{48b58d5d31e448d1a63fe3c682676fd5,

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

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

year = "1979",

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

language = "English (US)",

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

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

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

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

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

M3 - Article

AN - SCOPUS:49249152267

SN - 0012-365X

VL - 26

SP - 177

EP - 184

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

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