Geodesic
On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
Zoltán Lóránt Nagy1 ; Balázs Patkós2
1MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pazmany P. setany 1/C
2MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pazmany P. setany 1/C, Hungary and Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences.
The electronic journal of combinatorics, Tome 22 (2015) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study the function $M(n,k)$ which denotes the number of maximal $k$-uniform intersecting families $\mathcal{F}\subseteq \binom{[n]}{k}$. Improving a bound of Balogh, Das, Delcourt, Liu and Sharifzadeh on $M(n,k)$, we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$, $M(n,k) =n^{\Theta(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach.The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters.
DOI : 10.37236/4955
Classification : 05A16, 05D05
Mots-clés : maximal, uniform intersecting system, set pair, cross-intersecting, Bollobás theorem

Zoltán Lóránt Nagy  1   ; Balázs Patkós  2

1 MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pazmany P. setany 1/C
2 MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pazmany P. setany 1/C, Hungary and Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences. 
@article{10_37236_4955,
     author = {Zolt\'an L\'or\'ant Nagy and Bal\'azs Patk\'os},
     title = {On the number of maximal intersecting \(k\)-uniform families and further applications of {Tuza's} set pair method},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {1},
     doi = {10.37236/4955},
     zbl = {1310.05018},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4955/}
}
TY  - JOUR
AU  - Zoltán Lóránt Nagy
AU  - Balázs Patkós
TI  - On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4955/
DO  - 10.37236/4955
ID  - 10_37236_4955
ER  - 
%0 Journal Article
%A Zoltán Lóránt Nagy
%A Balázs Patkós
%T On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4955/
%R 10.37236/4955
%F 10_37236_4955
Zoltán Lóránt Nagy; Balázs Patkós. On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/4955

Cité par Sources :