The unbalance of set systems (Q1014818)

From MaRDI portal





scientific article; zbMATH DE number 5549534
Language Label Description Also known as
English
The unbalance of set systems
scientific article; zbMATH DE number 5549534

    Statements

    The unbalance of set systems (English)
    0 references
    0 references
    0 references
    29 April 2009
    0 references
    The authors present the following nice result: If the unbalance of an intersecting family of sets \( \mathcal{F} \) is defined as \( u(\mathcal{F}) = |\mathcal{F}|-d(\mathcal{F}) \) where \( d(\mathcal(F)=\max|\{F\in\mathcal{F}:x\in F\}| \), where the maximum is taken over all vertices x, then for k-uniform intersecting families \( u(\mathcal{F}) \leqq \binom{n-3}{k-2} \) for \( n \geqq 6k^3 \), where \(n\) is the number of vertices and \(k\) is the cardinality of the sets in the family. Furthermore the authors characterize the families where equality holds. Part of the proof needs a small revision: case 1 at page 365 should be handled as follows as I learned from private correspondence with one of the authors: The intersection of all G meeting \(\{t_1,t_2,t_3\}\) not containing \(x\) and \(t_4\) must be empty for otherwise it contains a point \(z\) and then \(x,t_4,z\) could replace \(t_1,t_2,t_3\) in the transversal contradicting the minimality of the transversal. In the paper the existence of sets G meeting \(\{t_1,t_2,t_3\}\) and not containing \(x,t_4\) is argued. Pick such a \(G_1\). Now the intersection of \(G\) and \(H\) must contain a point say \(x_1\). Since the intersection of all such G is empty there must be such a set \(G_2\) not containing \(x_1\). Also \(G_2\) and \(H\) should meet, say in a point \(x_2\). Now there are at most \(k^3\) ways to choose the triplet \(x,x_1,x_2\) and there are at most \(\binom{n-4}{k-4}\) ways to complete an H containing \(t_4,x,x_1,x_2\).This bounds the number of H containing \(t_4\) that can be constructed in this way by \(k^3\binom{n-4}{k-4}\) sharpening the bound given in this case in the paper.
    0 references
    unbalance
    0 references
    intersecting set systems
    0 references
    intersecting families
    0 references

    Identifiers