A problem of Laczkovich: how dense are set systems with no large independent sets? (Q2630826): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q178041
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Péter Komjáth / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.apal.2015.09.004 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2372950453 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4087192 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial set theory: Partition relations for cardinals / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3344197 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Distinct representatives of subsets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ideals and differential operators in the ring of polynomials of infinitely many variables / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3880849 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partitioning pairs of countable ordinals / rank
 
Normal rank

Latest revision as of 07:41, 12 July 2024

scientific article
Language Label Description Also known as
English
A problem of Laczkovich: how dense are set systems with no large independent sets?
scientific article

    Statements

    A problem of Laczkovich: how dense are set systems with no large independent sets? (English)
    0 references
    22 July 2016
    0 references
    A system \({\mathcal H} \subseteq [\lambda]^{<\omega}\) is \textit{\(\kappa\)-dense} (\textit{\(\kappa\)-strongly dense}) if for every \(\kappa\)-sized \(X \subseteq \lambda\), there is an (arbitrarily large) member of \({\mathcal H}\) which is contained in \(X\). When \(\kappa=\lambda\), it is called \textit{dense} (\textit{strongly dense}). The case \(\kappa=\lambda=\omega_1\) is a question raised by \textit{M. Laczkovich} [Period. Math. Hung. 69, No. 2, 109--119 (2014; Zbl 1349.13043)]. A variation of this function appeared in the paper of \textit{P. Erdős} et al. [in: Infinite and finite sets. To Paul Erdős on his 60th birthday. Vol. I, II, III. Amsterdam - London: North-Holland Publishing Company. 425--513 (1975; Zbl 0324.04005)]. This paper investigate the growing rate of the function \(L_{\mathcal H}(n) = \max \{|{\mathcal H} \cap {\mathcal P}(x)| : x \in [\lambda]^n\}\). \hskip1em The author shows that for every strongly dense system, \(L_{\mathcal H}(n) /n \to \infty\) (Theorem 2) and there is one such that \(L_{\mathcal H}(n) = O(n^2)\) (Theorem 1). The possible growing rates of \(L_{\mathcal H}(n)\) (in particular the case \(L_{\mathcal H}(n)=O(n f(n))\)) for various monotic \(f: \omega \to \omega\) such that \(f(n) \to \infty\) are discussed in Theorems 3--6. In Theorem 9, it is shown that when \(\lambda>\omega_1\), for every nonuniform strongly dense \({\mathcal H}\), \(L_{\mathcal H}(n)>c n^2\), for some constant \(c\). The author also shows that under GCH, if \(1<r<\omega\), \({\mathcal H}\) is \(\kappa\)-dense in \(\kappa^{+r}\), then \(L_{\mathcal H}(n)/n^r \to \infty\) for \(\kappa=\omega\) and \(L_{\mathcal H}(n) / c n^{r+1} \to \infty\) (for some constant \(c\)) for \(\kappa>\omega\). The situations in which \(L_{\mathcal H}(n)=O(n^2 f(n))\) for \(f: \omega \to \omega\) such that \(f(n) \to \infty\) are also discussed. In the last part of the paper, the author considers classes of set systems with large chromatic or coloring number. If \(\mathcal H\) is a system with uncountable coloring number, then \(L_{\mathcal H}(n)/n \to \infty\) (Theorem 17). In particular, if \(\mathcal H\) consists of \(k\)-tuples, then \(L_{\mathcal H}(n)> c_k n^{1+1/k}\) for sufficiently large \(n\) and some constant \(c_k\) (Theorem 19). Theorem 18 and 20 are results complementing the two theorems above.
    0 references
    0 references
    infinite set systems
    0 references
    chromatic number
    0 references
    independent set
    0 references
    forcing
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references