Geodesic
On the number of hyperedges in the hypergraph of lines and pseudo-discs
Chaya Keller ; Balázs Keszegh1 ; Dömötör Pálvölgyi2
1Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences and MTA-ELTE Lend\"ulet Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University, Budapest
2MTA-ELTE Lendület Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University, Budapest
The electronic journal of combinatorics, Tome 29 (2022) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Consider a hypergraph whose vertex set is a family of $n$ lines in general position in the plane, and whose hyperedges are induced by intersections with a family of pseudo-discs. We prove that the number of $t$-hyperedges is bounded by $O_t(n^2)$ and that the total number of hyperedges is bounded by $O(n^3)$. Both bounds are tight.
DOI : 10.37236/10424
Classification : 05C30, 05C65, 05C10, 05C15
Mots-clés : VC-dimension, 3-hyperedges

Chaya Keller    ; Balázs Keszegh  1   ; Dömötör Pálvölgyi  2

1 Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences and MTA-ELTE Lend\"ulet Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University, Budapest
2 MTA-ELTE Lendület Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University, Budapest 
@article{10_37236_10424,
     author = {Chaya Keller and Bal\'azs Keszegh and D\"om\"ot\"or P\'alv\"olgyi},
     title = {On the number of hyperedges in the hypergraph of lines and pseudo-discs},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {3},
     doi = {10.37236/10424},
     zbl = {1494.05059},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10424/}
}
TY  - JOUR
AU  - Chaya Keller
AU  - Balázs Keszegh
AU  - Dömötör Pálvölgyi
TI  - On the number of hyperedges in the hypergraph of lines and pseudo-discs
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10424/
DO  - 10.37236/10424
ID  - 10_37236_10424
ER  - 
%0 Journal Article
%A Chaya Keller
%A Balázs Keszegh
%A Dömötör Pálvölgyi
%T On the number of hyperedges in the hypergraph of lines and pseudo-discs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10424/
%R 10.37236/10424
%F 10_37236_10424
Chaya Keller; Balázs Keszegh; Dömötör Pálvölgyi. On the number of hyperedges in the hypergraph of lines and pseudo-discs. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10424

Cité par Sources :