Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Let L be a set of n axisparallel lines in R3. We are are interested in partitions of R3 by a set H of three planes such that each open cell in the arrangement A(H) is intersected by as few lines from L as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. * There are sets L of n axisparallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least ⌊n/3⌋  1 ≈ n/3 lines. * If we require the splitting planes to be axisparallel, then there are sets L of n axisparallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least (3/2) ⌊n/3⌋  1 ≈ (1/3 + 1/24) n lines. Furthermore, for any set L of n axisparallel lines, there exists a set H of three axisparallel splitting planes such that each open cell in A(H) intersects at most (7/18) n = (1/3 + 1/18) n lines. * For any set L of n axisparallel lines, there exists a set H of three axisparallel and mutually orthogonal splitting planes, such that each open cell in A(H) intersects at most ⌈5/12 n⌉ ≈ (1/3 + 1/12) n lines.more » « lessFree, publiclyaccessible full text available December 17, 2024

For an $r$uniform hypergraph $H$, let $\nu^{(m)}(H)$ denote the maximum size of a set $M$ of edges in $H$ such that every two edges in $M$ intersect in less than $m$ vertices, and let $\tau^{(m)}(H)$ denote the minimum size of a collection $C$ of $m$sets of vertices such that every edge in $H$ contains an element of $C$. The fractional analogues of these parameters are denoted by $\nu^{*(m)}(H)$ and $\tau^{*(m)}(H)$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $r$uniform hypergraph $H$, $\tau^{(r1)}(H)/\nu^{(r1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$. In this paper we prove bounds on the ratio between the parameters $\tau^{(m)}$ and $\nu^{(m)}$, and their fractional analogues. Our main result is that, for every $r$uniform hypergraph~$H$,\[ \tau^{*(r1)}(H)/\nu^{(r1)}(H) \le \begin{cases} \frac{3}{4}r  \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r  \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $r1$.We also prove that, for every $r$uniform hypergraph $H$, $\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$, where the Turán number $\operatorname{ex}_r(n, k)$ is the maximum number of edges in an $r$uniform hypergraph on $n$ vertices that does not contain a copy of the complete $r$uniform hypergraph on $k$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$.more » « less

Abstract A bipartite graph $H = \left (V_1, V_2; E \right )$ with $\lvert V_1\rvert + \lvert V_2\rvert = n$ is semilinear if $V_i \subseteq \mathbb {R}^{d_i}$ for some $d_i$ and the edge relation E consists of the pairs of points $(x_1, x_2) \in V_1 \times V_2$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $d_1 + d_2$ variables for some s . We show that for a fixed k , the number of edges in a $K_{k,k}$ free semilinear H is almost linear in n , namely $\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$ for any $\varepsilon> 0$ ; and more generally, $\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r1 + \varepsilon }\right )$ for a $K_{k, \dotsc ,k}$ free semilinear r partite r uniform hypergraph. As an application, we obtain the following incidence bound: given $n_1$ points and $n_2$ open boxes with axisparallel sides in $\mathbb {R}^d$ such that their incidence graph is $K_{k,k}$ free, there can be at most $O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of halfspaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the modeltheoretic trichotomy in o minimal structures (showing that the failure of an almostlinear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).more » « less