Oleg Pikhurko

The quadratic Brown--Erdős--Sós problem for 3-uniform hypergraphs with 8 and 9 edges

Levente Bodnár, Oleg Pikhurko, Shumin Sun +2

The famous and actively studied problem of Brown--Erdős--Sós from 1973 asks for $f^{(r)} (n; s, k)$ , the maximum number of edges in an $r$ -graph with $n$ vertices in which no $s$ vert…

An improved bound on the minimum size of Turán $(r + 1, r)$ -systems

Jun Gao, Peiru Kuang, Oleg Pikhurko +1

For positive integers $n \geq s > r$ , let $T (n, s, r)$ denote the minimum number of edges in an $r$ -uniform hypergraph on $n$ vertices such that every $s$ -set of vertices contains at lea…

Intervals of uniform Turán densities

Heng Li, Xizhi Liu, Oleg Pikhurko

We prove that the set $Π_{∴, \infty}$ of uniform Turán densities of possibly infinite families of $3$ -graphs contains a terminal interval: there exists $δ > 0$ such that $[1-…

The inducibility of 6-vertex graphs

Levente Bodnár, Jun Gao, Jared León +3

The inducibility constant $λ_{F}$ of a graph $F$ is the asymptotically maximum induced density of $F$ in a growing sequence of graphs. This paper systematically investigates the ca…

Strong non-principality of positive codegree Turán density

Levente Bodnár, Jun Gao, Oleg Pikhurko +2

The \emph{minimum positive codegree} $δ_{k - 1}^{+} (G)$ of a $k$ -graph $G$ is the minimum, over all $(k - 1)$ -sets that lie in at least one edge, of the number of edges containing that s…

A note on the Ratio and Inertia Bounds for the $k$ -Independence Number

Jun Gao, Jie Ma, Oleg Pikhurko

The $k$ -th power $G^{k}$ of a graph $G$ is the graph on the same vertex set where the edge set consists of those pairs of distinct vertices of $G$ that are at distance at most $k$ fr…

Intervals of hypergraph Turán densities

Xizhi Liu, Oleg Pikhurko

We prove that, for every integer $r \geq 3$ , the set $Π_{\infty}^{(r)}$ of Turán densities of (possibly infinite) families of $r$ -graphs contains non-degenerate intervals, including an…

On problems of Erdős and Baumann-Briggs on minimising the density of $s$ -cliques in graphs with forbidden subgraphs

Levente Bodnár, Oleg Pikhurko

Using flag algebras, we prove that the minimum density of $8$ -cliques in a large graph without an independent set of size $3$ is $491411/268435456 + o (1)$ , thus resolving a new case…

Rational codegree Turán density of hypergraphs

Jun Gao, Oleg Pikhurko, Mingyuan Rong +1

Let $H$ be a $k$ -graph (i.e. a $k$ -uniform hypergraph). Its minimum codegree $δ_{k - 1} (H)$ is the largest integer $t$ such that every $(k - 1)$ -subset of $V (H)$ is contained in at lea…

Covering large-dimensional Euclidean spaces by random translates of a given convex body

Boris Bukh, Jun Gao, Xizhi Liu +2

Determining the minimum density of a covering of $R^{n}$ by Euclidean unit balls as $n \to \infty$ is a major open problem, with the best known results being the lower bound…

Semi-inducibility of 4-vertex graphs

Levente Bodnár, Oleg Pikhurko

For a graph $H$ whose edges are coloured blue or red, the $H$ -semi-inducibility problem asks for the maximum, over all graphs $G$ of given order $n$ , of the number of injections fr…

Some exact inducibility-type results for graphs via flag algebras

Levente Bodnár, Oleg Pikhurko

The $(κ, ℓ)$ -edge-inducibility problem asks for the maximum number of $κ$ -subsets inducing exactly $ℓ$ edges that a graph of given order $n$ can have. Using flag algebras and…

The Turán density of short tight cycles

Levente Bodnár, Jared León, Xizhi Liu +1

The $3$ -uniform tight $ℓ$ -cycle $C_{ℓ}^{3}$ is the $3$ -graph on ${1, \dots, ℓ}$ consisting of all $ℓ$ consecutive triples in the cyclic order. Let $C$ be either…

Convergence of spectra of digraph limits

Jan Grebík, Daniel Král', Xizhi Liu +2

The relation between densities of cycles and the spectrum of a graphon, which implies that the spectra of convergent graphons converge, fundamentally relies on the self-adjointness…

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Oleg Pikhurko, Shumin Sun

Let $f^{(r)} (n; s, k)$ be the maximum number of edges in an $n$ -vertex $r$ -uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 197…

Some exact values of the inducibility and statistics constants for hypercubes

Levente Bodnár, Oleg Pikhurko

We consider two types of problems: maximising, over subsets $S \subseteq {0, 1}^{n}$ , the density of $d$ -subcubes $C$ in the $n$ -hypercube graph that span a subgraph such that $S\cap…

A note on the minimum size of Turán systems

Xizhi Liu, Oleg Pikhurko

For positive integers $n \geq s > r$ , a \emph{Turán $(n, s, r)$ -system} is an $n$ -vertex $r$ -graph in which every set of $s$ vertices contains at least one edge. Let $T (n, s, r)$ denote…

The Turán density of the tight 5-cycle minus one edge

Levente Bodnár, Jared León, Xizhi Liu +1

Let the tight $ℓ$ -cycle minus one edge $C_{ℓ}^{3 -}$ be the $3$ -graph on ${1, \dots, ℓ}$ consisting of $ℓ - 1$ consecutive triples in the cyclic order. We show that, for eve…

Phase transition of degenerate Turán problems in $p$ -norms

Jun Gao, Xizhi Liu, Jie Ma +1

For a positive real number $p$ , the $p$ -norm $∥ G ∥_{p}$ of a graph $G$ is the sum of the $p$ -th powers of all vertex degrees. We study the maximum $p$ -norm $\ma…

New bounds for the optimal density of covering single-insertion codes via the Turán density

Oleg Pikhurko, Oleg Verbitsky, Maksim Zhukovskii

We prove that the density of any covering single-insertion code $C \subseteq X^{r}$ over the $n$ -symbol alphabet $X$ cannot be smaller than $1/ r + δ_{r}$ for some positive real $δ_{r}$ not…

Nondegenerate Turán problems under $(t, p)$ -norms

Wanfang Chen, Daniel Iľkovič, Jared León +2

Given integers $r > t \geq 1$ and a real number $p > 0$ , the $(t, p)$ -norm $∥ H ∥_{t, p}$ of an $r$ -graph $H$ is the sum of the $p$ -th power o…

Constructions of Turán systems that are tight up to a multiplicative constant

Oleg Pikhurko

For positive integers $n \geq s > r$ , the Turán function $T (n, s, r)$ is the smallest size of an r-graph with n vertices such that every set of s vertices contains at least one edge. Al…

New lower bound on ball packing density in high-dimensional hyperbolic spaces

Irene Gil Fernández, Jaehoon Kim, Hong Liu +1

We present a new lower bound on the Bowen-Radin maximal density of radius-R ball packings in the m-dimensional hyperbolic space, improving on the basic covering bound by factor Ω(m…