On disjointly representable sets (Q790112): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Peter Frankl / rank | |||
Property / reviewed by | |||
Property / reviewed by: Péter Komjáth / rank | |||
Property / author | |||
Property / author: Peter Frankl / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Péter Komjáth / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On generalized graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On coloring graphs to maximize the proportion of multicolored k-edges / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An extremal problem in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Intersection Theorems for Systems of Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the trace of finite sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of sets in a null t-design / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5642587 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solution of a problem of A. Ehrenfeucht and J. Mycielski / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the density of families of sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4745841 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the theory of graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 12:07, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On disjointly representable sets |
scientific article |
Statements
On disjointly representable sets (English)
0 references
1984
0 references
A set-system \(E_ 1,...,E_ k\subset X\) is disjointly representable if there exist \(x_ 1,...,x_ k\in X\) such that \(x_ i\in E_ j\) if and only if \(i\neq j\). f(r,k) is the maximal size of an r-uniform system containing no k disjointly representable members. It is proved that \(f(r,3)=\lfloor(r+2)/2\rfloor \cdot \lceil(r+2)/2\rceil\), and the (unique) extremal system is described. For \(k>3\) asymptotically sharp bounds are given. The sets \(E_ 1,...,E_ k\subset X\) are disjointly t- representable if there are t-element \(X_ i\subset E_ i\) such that \(X_ i\cap E_ j=\emptyset\) whenever \(i\neq j\). \(f_ t^{\ell}(r,k)\) is the maximum size of an r-uniform system without k disjointly t- representable members and without a \(\Delta\)-system of size \(\ell\) and with kernel of cardinality \(>r-t\). Then \(cr^{(k-1)t}<f_ t^{\ell}(r,k)<c'r^{kt-1}\) where \(0<c,c'\) depend on k,\(\ell,t\). An analogue of Sauer's theorem on traces of systems is also proved.
0 references
extremal hypergraph problems
0 references
delta-systems
0 references
representable systems
0 references
Turán problem
0 references