Zobrazeno 1 - 10
of 372
pro vyhledávání: '"Á Pálvölgyi"'
Autor:
Jung, Attila, Pálvölgyi, Dömötör
We prove that fractional Helly and $(p,q)$-theorems imply $(\aleph_0,q)$-theorems in an entirely abstract setting. We give a plethora of applications, including reproving almost all earlier $(\aleph_0,q)$-theorems about geometric hypergraphs that wer
Externí odkaz:
http://arxiv.org/abs/2412.04066
Assume two finite families $\mathcal A$ and $\mathcal B$ of convex sets in $\mathbb{R}^3$ have the property that $A\cap B\ne \emptyset$ for every $A \in \mathcal A$ and $B\in \mathcal B$. Is there a constant $\gamma >0$ (independent of $\mathcal A$ a
Externí odkaz:
http://arxiv.org/abs/2409.06472
The study of geometric hypergraphs gave rise to the notion of $ABAB$-free hypergraphs. A hypergraph $\mathcal{H}$ is called $ABAB$-free if there is an ordering of its vertices such that there are no hyperedges $A,B$ and vertices $v_1,v_2,v_3,v_4$ in
Externí odkaz:
http://arxiv.org/abs/2409.01680
Autor:
Keszegh, Balázs, Pálvölgyi, Dömötör
Geometric motivations warranted the study of hypergraphs on ordered vertices that have no pair of hyperedges that induce an alternation of some given length. Such hypergraphs are called ABA-free, ABAB-free and so on. Since then various coloring and o
Externí odkaz:
http://arxiv.org/abs/2406.13321
Autor:
Bhore, Sujoy, Keszegh, Balázs, Kupavskii, Andrey, Le, Hung, Louvet, Alexandre, Pálvölgyi, Dömötör, Tóth, Csaba D.
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with $O(n\log(n))$ edges (SICOMP 20
Externí odkaz:
http://arxiv.org/abs/2404.05045
Autor:
Jung, Attila, Pálvölgyi, Dömötör
We prove a fractional Helly theorem for $k$-flats intersecting fat convex sets. A family $\mathcal{F}$ of sets is said to be $\rho$-fat if every set in the family contains a ball and is contained in a ball such that the ratio of the radii of these ba
Externí odkaz:
http://arxiv.org/abs/2311.15646
Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erd\H os--Szemer\'edi conjecture, recently
Externí odkaz:
http://arxiv.org/abs/2310.16701
In a graph $G$, the $2$-neighborhood of a vertex set $X$ consists of all vertices of $G$ having at least $2$ neighbors in $X$. We say that a bipartite graph $G(A,B)$ satisfies the double Hall property if $|A|\geq2$, and every subset $X \subseteq A$ o
Externí odkaz:
http://arxiv.org/abs/2310.02909
Autor:
Gerbner, Dániel, Keszegh, Balázs, Nagy, Dániel T., Nagy, Kartal, Pálvölgyi, Dömötör, Patkós, Balázs, Wiener, Gábor
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and
Externí odkaz:
http://arxiv.org/abs/2309.13678
Autor:
Pálvölgyi, Dömötör
We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the firs
Externí odkaz:
http://arxiv.org/abs/2309.04603