Intersecting families, signed sets, and injection
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420392" target="_blank" >RIV/00216208:11320/20:10420392 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=iCD-l85yeV" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=iCD-l85yeV</a>
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Intersecting families, signed sets, and injection
Popis výsledku v původním jazyce
Let k, r, n >= 1 be integers, and let S-n,S-k,S-r be the family of r-signed k-sets on [n] = {1, ..., n} given by S-n,S-k,S-r = {{(x(1), ..., a(1)), ..., (x(k), a(k))} : {x(1), ..., x(k)} is an element of (([n])(k)), a(1), ..., a(k) is an element of [r]}. A family A subset of S-n,S-k,S-r is intersecting if A, B is an element of A implies A boolean AND B not equal empty set. A well-known result (first stated by Meyer and proved using different methods by Deza and Frankl, and Bollobds and Leader) states that if A subset of S-n,S-k,S-r is intersecting, r >= 2 and 1 <= k <= n, then vertical bar A vertical bar < r(k-1) ((n-1)(k-1)). We provide a proof of this result by injection (in the same spirit as Frankl and Furedi's and Hurlbert and Kamat's injective proofs of the Erdos-Ko-Rado Theorem, and Frankl's and Hurlbert and Kamat's injective proofs of the Hilton-Milner Theorem) whenever r >= 2 and 1 <= k <= n/2, leaving open only some cases when k <= n.
Název v anglickém jazyce
Intersecting families, signed sets, and injection
Popis výsledku anglicky
Let k, r, n >= 1 be integers, and let S-n,S-k,S-r be the family of r-signed k-sets on [n] = {1, ..., n} given by S-n,S-k,S-r = {{(x(1), ..., a(1)), ..., (x(k), a(k))} : {x(1), ..., x(k)} is an element of (([n])(k)), a(1), ..., a(k) is an element of [r]}. A family A subset of S-n,S-k,S-r is intersecting if A, B is an element of A implies A boolean AND B not equal empty set. A well-known result (first stated by Meyer and proved using different methods by Deza and Frankl, and Bollobds and Leader) states that if A subset of S-n,S-k,S-r is intersecting, r >= 2 and 1 <= k <= n, then vertical bar A vertical bar < r(k-1) ((n-1)(k-1)). We provide a proof of this result by injection (in the same spirit as Frankl and Furedi's and Hurlbert and Kamat's injective proofs of the Erdos-Ko-Rado Theorem, and Frankl's and Hurlbert and Kamat's injective proofs of the Hilton-Milner Theorem) whenever r >= 2 and 1 <= k <= n/2, leaving open only some cases when k <= n.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA19-21082S" target="_blank" >GA19-21082S: Grafy a jejich algebraické vlastnosti</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Australasian Journal of Combinatorics [online]
ISSN
2202-3518
e-ISSN
—
Svazek periodika
76
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
AU - Austrálie
Počet stran výsledku
6
Strana od-do
226-231
Kód UT WoS článku
000501567800013
EID výsledku v databázi Scopus
2-s2.0-85078533202