Intersecting families, signed sets, and injection

Result code in 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>
Result on the web
<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
—

Result language
angličtina
Original language name
Intersecting families, signed sets, and injection
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA19-21082S" target="_blank" >GA19-21082S: Graphs and their algebraic properties</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)