Loading…
Rainbow Matchings and Algebras of Sets
Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence, 2002 ) asks the following question in the context of algebras of sets: What is the smallest number v = v ( n ) such that, if A 1 , … , A n are n equivalence relations on a common finite...
Saved in:
| Published in: | Graphs and combinatorics 2017-03, Vol.33 (2), p.473-484 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3 |
| container_end_page | 484 |
| container_issue | 2 |
| container_start_page | 473 |
| container_title | Graphs and combinatorics |
| container_volume | 33 |
| creator | Nivasch, Gabriel Omri, Eran |
| description | Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence,
2002
) asks the following question in the context of algebras of sets: What is the smallest number
v
=
v
(
n
)
such that, if
A
1
,
…
,
A
n
are
n
equivalence relations on a common finite ground set
X
, such that for each
i
there are at least
v
elements of
X
that belong to
A
i
-equivalence classes of size larger than 1, then
X
has a rainbow matching—a set of 2
n
distinct elements
a
1
,
b
1
,
…
,
a
n
,
b
n
, such that
a
i
is
A
i
-equivalent to
b
i
for each
i
? Grinblat has shown that
v
(
n
)
≤
10
n
/
3
+
O
(
n
)
. He asks whether
v
(
n
)
=
3
n
-
2
for all
n
≥
4
. In this paper we improve the upper bound (for all large enough
n
) to
v
(
n
)
≤
16
n
/
5
+
O
(
1
)
. |
| doi_str_mv | 10.1007/s00373-017-1764-9 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1884121882</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1884121882</sourcerecordid><originalsourceid>FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMoWFd_gLeexEt0Jh9Nc1wWv2BF8OMc0iatXbrtmnQR_71Z6tnLDMw878A8hFwi3CCAuo0AXHEKqCiqQlB9RDIUXFKpURyTDDRi2qI-JWcxbgBAooCMXL3abqjG7_zZTvVnN7Qxt4PLl33rq2BjPjb5m5_iOTlpbB_9xV9fkI_7u_fVI12_PDytlmtac4YTVQ5ErbnVTinhmZYFL7z1ErmTQipkBYqqdGnGNGMSnNW8hAqasmicrWq-INfz3V0Yv_Y-Tmbbxdr3vR38uI8Gy1IgS5UlFGe0DmOMwTdmF7qtDT8GwRycmNmJSU7MwYnRKcPmTEzs0PpgNuM-DOmjf0K_RMFhqw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1884121882</pqid></control><display><type>article</type><title>Rainbow Matchings and Algebras of Sets</title><source>Springer Nature</source><creator>Nivasch, Gabriel ; Omri, Eran</creator><creatorcontrib>Nivasch, Gabriel ; Omri, Eran</creatorcontrib><description>Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence,
2002
) asks the following question in the context of algebras of sets: What is the smallest number
v
=
v
(
n
)
such that, if
A
1
,
…
,
A
n
are
n
equivalence relations on a common finite ground set
X
, such that for each
i
there are at least
v
elements of
X
that belong to
A
i
-equivalence classes of size larger than 1, then
X
has a rainbow matching—a set of 2
n
distinct elements
a
1
,
b
1
,
…
,
a
n
,
b
n
, such that
a
i
is
A
i
-equivalent to
b
i
for each
i
? Grinblat has shown that
v
(
n
)
≤
10
n
/
3
+
O
(
n
)
. He asks whether
v
(
n
)
=
3
n
-
2
for all
n
≥
4
. In this paper we improve the upper bound (for all large enough
n
) to
v
(
n
)
≤
16
n
/
5
+
O
(
1
)
.</description><identifier>ISSN: 0911-0119</identifier><identifier>EISSN: 1435-5914</identifier><identifier>DOI: 10.1007/s00373-017-1764-9</identifier><language>eng</language><publisher>Tokyo: Springer Japan</publisher><subject>Algebra ; Combinatorial analysis ; Combinatorics ; Engineering Design ; Equivalence ; Grounds ; Mathematical analysis ; Mathematics ; Mathematics and Statistics ; Original Paper ; Rainbows ; Texts ; Translations</subject><ispartof>Graphs and combinatorics, 2017-03, Vol.33 (2), p.473-484</ispartof><rights>Springer Japan 2017</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3</citedby><cites>FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Nivasch, Gabriel</creatorcontrib><creatorcontrib>Omri, Eran</creatorcontrib><title>Rainbow Matchings and Algebras of Sets</title><title>Graphs and combinatorics</title><addtitle>Graphs and Combinatorics</addtitle><description>Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence,
2002
) asks the following question in the context of algebras of sets: What is the smallest number
v
=
v
(
n
)
such that, if
A
1
,
…
,
A
n
are
n
equivalence relations on a common finite ground set
X
, such that for each
i
there are at least
v
elements of
X
that belong to
A
i
-equivalence classes of size larger than 1, then
X
has a rainbow matching—a set of 2
n
distinct elements
a
1
,
b
1
,
…
,
a
n
,
b
n
, such that
a
i
is
A
i
-equivalent to
b
i
for each
i
? Grinblat has shown that
v
(
n
)
≤
10
n
/
3
+
O
(
n
)
. He asks whether
v
(
n
)
=
3
n
-
2
for all
n
≥
4
. In this paper we improve the upper bound (for all large enough
n
) to
v
(
n
)
≤
16
n
/
5
+
O
(
1
)
.</description><subject>Algebra</subject><subject>Combinatorial analysis</subject><subject>Combinatorics</subject><subject>Engineering Design</subject><subject>Equivalence</subject><subject>Grounds</subject><subject>Mathematical analysis</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Original Paper</subject><subject>Rainbows</subject><subject>Texts</subject><subject>Translations</subject><issn>0911-0119</issn><issn>1435-5914</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMoWFd_gLeexEt0Jh9Nc1wWv2BF8OMc0iatXbrtmnQR_71Z6tnLDMw878A8hFwi3CCAuo0AXHEKqCiqQlB9RDIUXFKpURyTDDRi2qI-JWcxbgBAooCMXL3abqjG7_zZTvVnN7Qxt4PLl33rq2BjPjb5m5_iOTlpbB_9xV9fkI_7u_fVI12_PDytlmtac4YTVQ5ErbnVTinhmZYFL7z1ErmTQipkBYqqdGnGNGMSnNW8hAqasmicrWq-INfz3V0Yv_Y-Tmbbxdr3vR38uI8Gy1IgS5UlFGe0DmOMwTdmF7qtDT8GwRycmNmJSU7MwYnRKcPmTEzs0PpgNuM-DOmjf0K_RMFhqw</recordid><startdate>20170301</startdate><enddate>20170301</enddate><creator>Nivasch, Gabriel</creator><creator>Omri, Eran</creator><general>Springer Japan</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>KR7</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20170301</creationdate><title>Rainbow Matchings and Algebras of Sets</title><author>Nivasch, Gabriel ; Omri, Eran</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algebra</topic><topic>Combinatorial analysis</topic><topic>Combinatorics</topic><topic>Engineering Design</topic><topic>Equivalence</topic><topic>Grounds</topic><topic>Mathematical analysis</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Original Paper</topic><topic>Rainbows</topic><topic>Texts</topic><topic>Translations</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Nivasch, Gabriel</creatorcontrib><creatorcontrib>Omri, Eran</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Graphs and combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Nivasch, Gabriel</au><au>Omri, Eran</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Rainbow Matchings and Algebras of Sets</atitle><jtitle>Graphs and combinatorics</jtitle><stitle>Graphs and Combinatorics</stitle><date>2017-03-01</date><risdate>2017</risdate><volume>33</volume><issue>2</issue><spage>473</spage><epage>484</epage><pages>473-484</pages><issn>0911-0119</issn><eissn>1435-5914</eissn><abstract>Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence,
2002
) asks the following question in the context of algebras of sets: What is the smallest number
v
=
v
(
n
)
such that, if
A
1
,
…
,
A
n
are
n
equivalence relations on a common finite ground set
X
, such that for each
i
there are at least
v
elements of
X
that belong to
A
i
-equivalence classes of size larger than 1, then
X
has a rainbow matching—a set of 2
n
distinct elements
a
1
,
b
1
,
…
,
a
n
,
b
n
, such that
a
i
is
A
i
-equivalent to
b
i
for each
i
? Grinblat has shown that
v
(
n
)
≤
10
n
/
3
+
O
(
n
)
. He asks whether
v
(
n
)
=
3
n
-
2
for all
n
≥
4
. In this paper we improve the upper bound (for all large enough
n
) to
v
(
n
)
≤
16
n
/
5
+
O
(
1
)
.</abstract><cop>Tokyo</cop><pub>Springer Japan</pub><doi>10.1007/s00373-017-1764-9</doi><tpages>12</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0911-0119 |
| ispartof | Graphs and combinatorics, 2017-03, Vol.33 (2), p.473-484 |
| issn | 0911-0119 1435-5914 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_1884121882 |
| source | Springer Nature |
| subjects | Algebra Combinatorial analysis Combinatorics Engineering Design Equivalence Grounds Mathematical analysis Mathematics Mathematics and Statistics Original Paper Rainbows Texts Translations |
| title | Rainbow Matchings and Algebras of Sets |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-02T00%3A08%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Rainbow%20Matchings%20and%20Algebras%20of%20Sets&rft.jtitle=Graphs%20and%20combinatorics&rft.au=Nivasch,%20Gabriel&rft.date=2017-03-01&rft.volume=33&rft.issue=2&rft.spage=473&rft.epage=484&rft.pages=473-484&rft.issn=0911-0119&rft.eissn=1435-5914&rft_id=info:doi/10.1007/s00373-017-1764-9&rft_dat=%3Cproquest_cross%3E1884121882%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c321t-7d04c93a9d774e295636eae513d545712614b8d6ea292250da9380b0f86fdabc3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1884121882&rft_id=info:pmid/&rfr_iscdi=true |