Zarankiewicz’s problem for semilinear hypergraphs
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2021-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509421000529/type/journal_article |
| _version_ | 1811156199954972672 |
|---|---|
| author | Abdul Basit Artem Chernikov Sergei Starchenko Terence Tao Chieu-Minh Tran |
| author_facet | Abdul Basit Artem Chernikov Sergei Starchenko Terence Tao Chieu-Minh Tran |
| author_sort | Abdul Basit |
| collection | DOAJ |
| description | 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^{r-1 + \varepsilon }\right )$
for a
$K_{k, \dotsc ,k}$
-free semilinear r-partite r-uniform hypergraph. |
| first_indexed | 2024-04-10T04:47:31Z |
| format | Article |
| id | doaj.art-c57db8dbb8e44e83bd1e36d1e7bfb079 |
| institution | Directory Open Access Journal |
| issn | 2050-5094 |
| language | English |
| last_indexed | 2024-04-10T04:47:31Z |
| publishDate | 2021-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj.art-c57db8dbb8e44e83bd1e36d1e7bfb0792023-03-09T12:34:52ZengCambridge University PressForum of Mathematics, Sigma2050-50942021-01-01910.1017/fms.2021.52Zarankiewicz’s problem for semilinear hypergraphsAbdul Basit0Artem Chernikov1https://orcid.org/0000-0002-9136-8737Sergei Starchenko2Terence Tao3https://orcid.org/0000-0002-0140-7641Chieu-Minh Tran4Department of Mathematics, Iowa State University, Ames, IA 50011, USA; E-mail: .Department of Mathematics, University of California Los Angeles, Los Angeles, CA 90095-1555, USA.Department of Mathematics, University of Notre Dame, Notre Dame, IN 46656, USA; E-mail: .Department of Mathematics, University of California Los Angeles, Los Angeles, CA 90095-1555, USA; E-mail: .Department of Mathematics, University of Notre Dame, Notre Dame, IN 46656, USA; E-mail: .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^{r-1 + \varepsilon }\right )$ for a $K_{k, \dotsc ,k}$ -free semilinear r-partite r-uniform hypergraph.https://www.cambridge.org/core/product/identifier/S2050509421000529/type/journal_article05D1052C1052C4503C4503C64Zarankiewicz’s problemsemilinear hypergraphsincidence combinatoricslocal modularityo-minimality |
| spellingShingle | Abdul Basit Artem Chernikov Sergei Starchenko Terence Tao Chieu-Minh Tran Zarankiewicz’s problem for semilinear hypergraphs Forum of Mathematics, Sigma 05D10 52C10 52C45 03C45 03C64 Zarankiewicz’s problem semilinear hypergraphs incidence combinatorics local modularity o-minimality |
| title | Zarankiewicz’s problem for semilinear hypergraphs |
| title_full | Zarankiewicz’s problem for semilinear hypergraphs |
| title_fullStr | Zarankiewicz’s problem for semilinear hypergraphs |
| title_full_unstemmed | Zarankiewicz’s problem for semilinear hypergraphs |
| title_short | Zarankiewicz’s problem for semilinear hypergraphs |
| title_sort | zarankiewicz s problem for semilinear hypergraphs |
| topic | 05D10 52C10 52C45 03C45 03C64 Zarankiewicz’s problem semilinear hypergraphs incidence combinatorics local modularity o-minimality |
| url | https://www.cambridge.org/core/product/identifier/S2050509421000529/type/journal_article |
| work_keys_str_mv | AT abdulbasit zarankiewiczsproblemforsemilinearhypergraphs AT artemchernikov zarankiewiczsproblemforsemilinearhypergraphs AT sergeistarchenko zarankiewiczsproblemforsemilinearhypergraphs AT terencetao zarankiewiczsproblemforsemilinearhypergraphs AT chieuminhtran zarankiewiczsproblemforsemilinearhypergraphs |