Source author record

Oliver Janzer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

10works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Asymptotics of the hypergraph bipartite Turán problem

For positive integers $s,t,r$ , let $K_{s,t}^{(r)}$ denote the $r$ -uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X,Y_1,\dots,Y_t$ , where $|X| = s$ and $|Y_1| = \dots = |Y_t| = r-1$ , and whose edge set is $\{\{x\} \cup Y_i: x \in X, 1\leq i\leq t\}$ . The study of the Turán function of $K_{s,t}^{(r)}$ received considerable interest in recent years. Our main results are as follows. First, we show that \begin{equation} \mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}) \end{equation} for all $s,t\geq 2$ and $r\geq 3$ , improving the power of $n$ in the previously best bound and resolving a question of Mubayi and Verstraëte about the dependence of $\mathrm{ex}(n,K_{2,t}^{(3)})$ on $t$ . Second, we show that this upper bound is tight when $r$ is even and $t \gg s$ . This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for $r = 3$ , namely that $\mathrm{ex}(n,K_{s,t}^{(3)}) = O_{s,t}(n^{3 - \frac{1}{s-1} - \varepsilon_s})$ (for all $s\geq 3$ ). This indicates that the behaviour of $\mathrm{ex}(n,K_{s,t}^{(r)})$ might depend on the parity of $r$ . Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Turán problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Kollár, Rónyai and Szabó.

preprint2022arXiv

Regular subgraphs of linear hypergraphs

We prove that the maximum number of edges in a 3-uniform linear hypergraph on $n$ vertices containing no 2-regular subhypergraph is $n^{1+o(1)}$ . This resolves a conjecture of Dellamonica, Haxell, Luczak, Mubayi, Nagle, Person, Rödl, Schacht and Verstraëte. We use this result to show that the maximum number of edges in a $3$ -uniform hypergraph on $n$ vertices containing no immersion of a closed surface is $n^{2+o(1)}$ . Furthermore, we present results on the maximum number of edges in $k$ -uniform linear hypergraphs containing no $r$ -regular subhypergraph.

preprint2022arXiv

Resolution of the Erdős-Sauer problem on regular subgraphs

In this paper we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$ -vertex graph can have without containing a $k$ -regular subgraph, for some fixed integer $k\geq 3$ . We prove that any $n$ -vertex graph with average degree at least $C_k\log \log n$ contains a $k$ -regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough. Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

preprint2022arXiv

Small subgraphs with large average degree

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$ , we prove that every graph on $n$ vertices with average degree at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with $n$ vertices and average degree at least $n^{1-\frac{2}{s}+\varepsilon}$ contains a subgraph of average degree at least $s$ on $O_{\varepsilon,s}(1)$ vertices, which is also optimal up to the constant hidden in the $O(.)$ notation, and resolves a conjecture of Verstraëte.

preprint2022arXiv

The Turán number of the grid

For a positive integer $t$ , let $F_t$ denote the graph of the $t\times t$ grid. Motivated by a 50-year-old conjecture of Erdős about Turán numbers of $r$ -degenerate graphs, we prove that there exists a constant $C=C(t)$ such that $\mathrm{ex}(n,F_t)\leq Cn^{3/2}$ . This bound is tight up to the value of $C$ . One of the interesting ingredients of our proof is a novel way of using the tensor power trick.

preprint2021arXiv

Long directed paths in Eulerian digraphs

An old conjecture of Bollobás and Scott asserts that every Eulerian directed graph with average degree $d$ contains a directed cycle of length at least $Ω(d)$ . The best known lower bound for this problem is $Ω(d^{1/2})$ by Huang, Ma, Shapira, Sudakov and Yuster. They asked whether this estimate can be improved at least for directed paths instead of cycles and whether one can find a long path starting from any vertex if the host digraph is connected. In this paper we break the $\sqrt{d}$ barrier, showing how to find a path of length $Ω(d^{1/2+1/40})$ from any vertex of a connected Eulerian digraph.

preprint2020arXiv

More on the extremal number of subdivisions

Given a graph $H$ , the extremal number $\mathrm{ex}(n,H)$ is the largest number of edges in an $H$ -free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K'_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$ , we show that $\mathrm{ex}(n, K'_{s,t}) = O(n^{3/2 - \frac{1}{2s}})$ . This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$ . Second, for any integers $s, k \geq 1$ , we show that $\mathrm{ex}(n, L) = Θ(n^{1 + \frac{s}{sk+1}})$ for a particular graph $L$ depending on $s$ and $k$ , answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erdős and Simonovits, which asserts that every rational number $r \in (1,2)$ is realisable in the sense that $\mathrm{ex}(n,H) = Θ(n^r)$ for some appropriate graph $H$ , giving infinitely many new realisable exponents and implying that $1 + 1/k$ is a limit point of realisable exponents for all $k \geq 1$ . Writing $H^k$ for the $k$ -subdivision of a graph $H$ , this result also implies that for any bipartite graph $H$ and any $k$ , there exists $δ> 0$ such that $\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - δ})$ , partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $\mathrm{ex}(n, H) = o(n^{2 - 1/r})$ .

preprint2020arXiv

Polynomial bound for the partition rank vs the analytic rank of tensors

A tensor defined over a finite field $\mathbb{F}$ has low analytic rank if the distribution of its values differs significantly from the uniform distribution. An order $d$ tensor has partition rank 1 if it can be written as a product of two tensors of order less than $d$ , and it has partition rank at most $k$ if it can be written as a sum of $k$ tensors of partition rank 1. In this paper, we prove that if the analytic rank of an order $d$ tensor is at most $r$ , then its partition rank is at most $f(r,d,|\mathbb{F}|)$ , where, for fixed $d$ and $\mathbb{F}$ , $f$ is a polynomial in $r$ . This is an improvement of a recent result of the author, where he obtained a tower-type bound. Prior to our work, the best known bound was an Ackermann-type function in $r$ and $d$ , though it did not depend on $\mathbb{F}$ . It follows from our results that a biased polynomial has low rank; there too we obtain a polynomial dependence improving the previously known Ackermann-type bound. A similar polynomial bound for the partition rank was obtained independently and simultaneously by Milićević.

preprint2019arXiv

The extremal number of longer subdivisions

For a multigraph $F$ , the $k$ -subdivision of $F$ is the graph obtained by replacing the edges of $F$ with pairwise internally vertex-disjoint paths of length $k+1$ . Conlon and Lee conjectured that if $k$ is even, then the $(k-1)$ -subdivision of any multigraph has extremal number $O(n^{1+\frac{1}{k}})$ , and moreover, that for any simple graph $F$ there exists $\varepsilon>0$ such that the $(k-1)$ -subdivision of $F$ has extremal number $O(n^{1+\frac{1}{k}-\varepsilon})$ . In this paper, we prove both conjectures.

preprint2019arXiv

The extremal number of the subdivisions of the complete bipartite graph

For a graph $F$ , the $k$ -subdivision of $F$ , denoted $F^k$ , is the graph obtained by replacing the edges of $F$ with internally vertex-disjoint paths of length $k$ . In this paper, we prove that $\mathrm{ex}(n,K_{s,t}^k)=O(n^{1+\frac{s-1}{sk}})$ , which is tight for $t$ sufficiently large. This settles a conjecture of Conlon--Janzer--Lee, and improves on a substantial body of work by Conlon--Janzer--Lee and Jiang--Qiu.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Oliver Janzer

Research overview

Is this your work?

10 publications

Asymptotics of the hypergraph bipartite Turán problem

Regular subgraphs of linear hypergraphs

Resolution of the Erdős-Sauer problem on regular subgraphs

Small subgraphs with large average degree

The Turán number of the grid

Long directed paths in Eulerian digraphs

More on the extremal number of subdivisions

Polynomial bound for the partition rank vs the analytic rank of tensors

The extremal number of longer subdivisions

The extremal number of the subdivisions of the complete bipartite graph

See the researcher in context

Building this map preview