Source author record

Oleg Pikhurko

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.MG math.LO Computational Complexity Computational Geometry Discrete Mathematics Logic in Computer Science math.OC

Catalog footprint

Research overview

30works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Rational codegree Turán density of hypergraphs

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 least $t$ edges of~ $H$ . The \emph{codegree Turán density} $γ(\mathcal{F})$ of a family $\mathcal{F}$ of $k$ -graphs is the infimum of $γ> 0$ such that every $k$ -graph $H$ on $n\to\infty$ vertices with $δ_{k-1}(H) \ge (γ+o(1))\, n$ contains some member of $\mathcal{F}$ as a subgraph. We prove that, for every integer $k\ge3$ and every rational number $α\in [0,1)$ , there exists a finite family of $k$ -graphs $\mathcal{F}$ such that $γ(\mathcal{F})=α$ . Also, for every $k \ge 3$ , we establish a strong version of non-principality, namely that there are two $k$ -graphs $F_1$ and $F_2$ such that the codegree Turán density of $\{F_1,F_2\}$ is strictly smaller than that of each $F_i$ . This answers a question of Mubayi and Zhao [J Comb Theory (A) 114 (2007) 1118--1132].

preprint2022arXiv

Disjoint isomorphic balanced clique subdivisions

A thoroughly studied problem in Extremal Graph Theory is to find the best possible density condition in a host graph $G$ for guaranteeing the presence of a particular subgraph $H$ in $G$ . One such classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that average degree $O(k^2)$ guarantees the existence of a $K_k$ -subdivision. We study two directions extending this result. On the one hand, Verstraëte conjectured that the quadratic bound $O(k^2)$ would guarantee already two vertex-disjoint isomorphic copies of a $K_k$ -subdivision. On the other hand, Thomassen conjectured that for each $k \in \mathbb{N}$ there is some $d = d(k)$ such that every graph with average degree at least $d$ contains a balanced subdivision of $K_k$ , that is, a copy of $K_k$ where the edges are replaced by paths of equal length. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on $d(k)$ remains open. In this paper, we show that the quadratic bound $O(k^2)$ suffices to force a balanced $K_k$ -subdivision. This gives the optimal bound on $d(k)$ needed in Thomassen's conjecture and implies the existence of $O(1)$ many vertex-disjoint isomorphic $K_k$ -subdivisions, confirming Verstraëte's conjecture in a strong sense.

preprint2022arXiv

Divisibility of Spheres with Measurable Pieces

For an $r$ -tuple $(γ_1,\ldots,γ_r)$ of special orthogonal $d\times d$ matrices, we say that the Euclidean $(d-1)$ -dimensional sphere $S^{d-1}$ is $(γ_1,\ldots,γ_r)$ -divisible if there is a subset $A\subseteq S^{d-1}$ such that its translations by the rotations $γ_1,\ldots,γ_r$ partition the sphere. Motivated by some old open questions of Mycielski and Wagon, we investigate the version of this notion where the set $A$ has to be measurable with respect to the spherical measure. Our main result shows that measurable divisibility is impossible for a "generic" (in various meanings) $r$ -tuple of rotations. This is in stark contrast to the recent result of Conley, Marks and Unger which implies that, for every "generic" $r$ -tuple, divisibility is possible with parts that have the property of Baire.

preprint2022arXiv

On a question of Vera T. Sós about size forcing of graphons

The $k$ -sample $\mathbb{G}(k,W)$ from a graphon $W:[0,1]^2\to [0,1]$ is the random graph on $\{1,\dots,k\}$ , where we sample $x_1,\dots,x_k\in [0,1]$ uniformly at random and make each pair $\{i,j\}\subseteq \{1,\dots,k\}$ an edge with probability $W(x_i,x_j)$ , with all these choices being mutually independent. Let the random variable $X_k(W)$ be the number of edges in $\mathbb{G}(k,W)$ . Vera T. Sós asked in 2012 whether two graphons $U,W$ are necessarily weakly isomorphic if the random variables $X_k(U)$ and $X_k(W)$ have the same distribution for every integer $k\ge 2$ . This question when one of the graphons $W$ is a constant function was answered positively by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós. Here we investigate the question when $W$ is a 2-step graphon and prove that the answer is positive for a 3-dimensional family of such graphons. We also present some related results.

preprint2021arXiv

Borel Combinatorics of Locally Finite Graphs

We provide a gentle introduction, aimed at non-experts, to Borel combinatorics that studies definable graphs on topological spaces. This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas. After giving some background material, we present in careful detail some basic tools and results on the existence of Borel satisfying assignments: Borel versions of greedy algorithms and augmenting procedures, local rules, Borel transversals, etc. Also, we present the construction of Andrew Marks of acyclic Borel graphs for which the greedy bound $Δ+1$ on the Borel chromatic number is best possible. In the remainder of the paper we briefly discuss various topics such as relations to LOCAL algorithms, measurable versions of Hall's marriage theorem and of Lovász Local Lemma, applications to equidecomposability, etc.

preprint2020arXiv

Measurable versions of Vizing's theorem

We establish two versions of Vizing's theorem for Borel multi-graphs whose vertex degrees and edge multiplicities are uniformly bounded by respectively $Δ$ and $π$ . The ``approximate'' version states that, for any Borel probability measure on the edge set and any $ε>0$ , we can properly colour all but $ε$ -fraction of edges with $Δ+π$ colours in a Borel way. The ``measurable'' version, which is our main result, states that if, additionally, the measure is invariant, then there is a measurable proper edge colouring of the whole edge set with at most $Δ+π$ colours.

preprint2020arXiv

The exact minimum number of triangles in graphs of given order and size

What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first non-trivial case of this problem in 1941. The problem was revived by Erdős in 1955; it is now known as the Erdős-Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from~ $1$ , which in this range confirms a conjecture of Lovász and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.

preprint2019arXiv

Minimizing the number of 5-cycles in graphs with given edge-density

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle $C_5$ . We show that every graph of order $n$ and size $\left( 1-\frac{1}{k}\right)\binom{n}{2}$ , where $k\ge 3$ is an integer, contains at least $\left( \frac{1}{10} -\frac{1}{2k} + \frac{1}{k^2} - \frac{1}{k^3} + \frac{2}{5 k^4} \right)n^5 +o(n^5)$ copies of $C_5$ . This bound is optimal, since a matching upper bound is given by the balanced complete $k$ -partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.

preprint2016arXiv

Kőnig's Line Coloring and Vizing's Theorems for Graphings

The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. Furthermore, as it was earlier shown by Kőnig, $d$ colors suffice if the graph is bipartite. We investigate the existence of measurable edge-colorings for graphings. A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence theory and measurable group theory. We show that every graphing of maximum degree $d$ admits a measurable edge-coloring with $d + O(\sqrt{d})$ colors; furthermore, if the graphing has no odd cycles, then $d+1$ colors suffice. In fact, if a certain conjecture about finite graphs that strengthens Vizing's theorem is true, then our method will show that $d+1$ colors are always enough.

preprint2016arXiv

Measurable circle squaring

Laczkovich proved that if bounded subsets $A$ and $B$ of $R^k$ have the same non-zero Lebesgue measure and the box dimension of the boundary of each set is less than $k$ , then there is a partition of $A$ into finitely many parts that can be translated to form a partition of $B$ . Here we show that it can be additionally required that each part is both Baire and Lebesgue measurable. As special cases, this gives measurable and translation-only versions of Tarski's circle squaring and Hilbert's third problem.

preprint2016arXiv

Supersaturation Problem for Color-Critical Graphs

The \emph{Turán function} $\ex(n,F)$ of a graph $F$ is the maximum number of edges in an $F$ -free graph with $n$ vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine $h_F(n,q)$ , the minimum number of copies of $F$ that a graph with $n$ vertices and $\ex(n,F)+q$ edges can have. We determine $h_F(n,q)$ asymptotically when $F$ is \emph{color-critical} (that is, $F$ contains an edge whose deletion reduces its chromatic number) and $q=o(n^2)$ . Determining the exact value of $h_F(n,q)$ seems rather difficult. For example, let $c_1$ be the limit superior of $q/n$ for which the extremal structures are obtained by adding some $q$ edges to a maximum $F$ -free graph. The problem of determining $c_1$ for cliques was a well-known question of Erd\H os that was solved only decades later by Lovász and Simonovits. Here we prove that $c_1>0$ for every {color-critical}~ $F$ . Our approach also allows us to determine $c_1$ for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.

preprint2015arXiv

Spherical sets avoiding a prescribed set of angles

Let $X$ be any subset of the interval $[-1,1]$ . A subset $I$ of the unit sphere in $R^n$ will be called \emph{ $X$ -avoiding} if $<u,v >\notin X$ for any $u,v \in I$ . The problem of determining the maximum surface measure of a $\{ 0 \}$ -avoiding set was first stated in a 1974 note by Witsenhausen; there the upper bound of $1/n$ times the surface measure of the sphere is derived from a simple averaging argument. A consequence of the Frankl-Wilson theorem is that this fraction decreases exponentially, but until now the $1/3$ upper bound for the case $n=3$ has not moved. We improve this bound to $0.313$ using an approach inspired by Delsarte's linear programming bounds for codes, combined with some combinatorial reasoning. In the second part of the paper, we use harmonic analysis to show that for $n\geq 3$ there always exists an $X$ -avoiding set of maximum measure. We also show with an example that a maximiser need not exist when $n=2$ .

preprint2015arXiv

The codegree threshold for 3-graphs with independent neighbourhoods

Given a family of 3-graphs $F$ , we define its codegree threshold $\mathrm{coex}(n, F)$ to be the largest number $d=d(n)$ such that there exists an $n$ -vertex 3-graph in which every pair of vertices is contained in at least $d$ 3-edges but which contains no member of $F$ as a subgraph. Let $F_{3,2}$ be the 3-graph on $\{a,b,c,d,e\}$ with 3-edges $\{abc,abd,abe,cde\}$ . In this paper, we give two proofs that $\mathrm{coex}(n, F_{3,2})= n/3 +o(n)$ , the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large $n$ : $\mathrm{coex}(n, F_{3,2})= \lfloor n/3 \rfloor -1$ if $n$ is congruent to $1$ modulo $3$ , and $\lfloor n/3 \rfloor$ otherwise. In addition we determine the set of codegree-extremal configurations.

preprint2015arXiv

The maximal length of a gap between r-graph Turán densities

The Turán density $π(\cal F)$ of a family $\cal F$ of $r$ -graphs is the limit as $n\to\infty$ of the maximum edge density of an $\cal F$ -free $r$ -graph on $n$ vertices. Erdos [Israel J. Math 2 (1964) 183--190] proved that no Turán density can lie in the open interval $(0,r!/r^r)$ . Here we show that any other open subinterval of $[0,1]$ avoiding Turán densities has strictly smaller length. In particular, this implies a conjecture of Grosu [E-print arXiv:1403.4653v1, 2014].

preprint2014arXiv

Asymptotic Structure of Graphs with the Minimum Number of Triangles

We consider the problem of minimizing the number of triangles in a graph of given order and size and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

preprint2014arXiv

Coloring d-Embeddable k-Uniform Hypergraphs

This paper extends the scenario of the Four Color Theorem in the following way. Let H(d,k) be the set of all k-uniform hypergraphs that can be (linearly) embedded into R^d. We investigate lower and upper bounds on the maximum (weak and strong) chromatic number of hypergraphs in H(d,k). For example, we can prove that for d>2 there are hypergraphs in H(2d-3,d) on n vertices whose weak chromatic number is Omega(log n/log log n), whereas the weak chromatic number for n-vertex hypergraphs in H(d,d) is bounded by O(n^((d-2)/(d-1))) for d>2.

preprint2014arXiv

Martin Gardner's minimum no-3-in-a-line problem

In Martin Gardner's October, 1976 Mathematical Games column in Scientific American, he posed the following problem: "What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal?" We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.

preprint2014arXiv

Measurable equidecompositions via combinatorics and group theory

We give a sketch of proof that any two (Lebesgue) measurable subsets of the unit sphere in $R^n$ , for $n\ge 3$ , with non-empty interiors and of the same measure are equidecomposable using pieces that are measurable.

preprint2014arXiv

Minimum number of monotone subsequences of length 4 in permutations

We show that for every sufficiently large $n$ , the number of monotone subsequences of length four in a permutation on $n$ points is at least $\binom{\lfloor n/3 \rfloor}{4} + \binom{\lfloor(n+1)/3\rfloor}{4} + \binom{\lfloor (n+2)/3\rfloor}{4}$ . Furthermore, we characterize all permutations on $[n]$ that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colorings of complete graphs with two colors, where the number of monochromatic $K_4$ 's is minimized. We show that all the extremal colorings must contain monochromatic $K_4$ 's only in one of the two colors. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

preprint2014arXiv

Monochromatic Clique Decompositions of Graphs

Let $G$ be a graph whose edges are coloured with $k$ colours, and $\mathcal H=(H_1,\dots , H_k)$ be a $k$ -tuple of graphs. A monochromatic $\mathcal H$ -decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a monochromatic copy of $H_i$ in colour $i$ , for some $1\le i\le k$ . Let $ϕ_{k}(n,\mathcal H)$ be the smallest number $ϕ$ , such that, for every order- $n$ graph and every $k$ -edge-colouring, there is a monochromatic $\mathcal H$ -decomposition with at most $ϕ$ elements. Extending the previous results of Liu and Sousa ["Monochromatic $K_r$ -decompositions of graphs", Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $\mathcal H$ is a clique and $n\ge n_0(\mathcal H)$ is sufficiently large.

preprint2013arXiv

Logical complexity of graphs: a survey

We discuss the definability of finite graphs in first-order logic with two relation symbols for adjacency and equality of vertices. The logical depth $D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number of variables occurring in such a sentence. The logical length $L(G)$ is the length of a shortest defining sentence. We survey known estimates for these graph parameters and discuss their relations to other topics (such as the efficiency of the Weisfeiler-Lehman algorithm in isomorphism testing, the evolution of a random graph, quantitative characteristics of the zero-one law, or the contribution of Frank Ramsey to the research on Hilbert's Entscheidungsproblem). Also, we trace the behavior of the descriptive complexity of a graph as the logic becomes more restrictive (for example, only definitions with a bounded number of variables or quantifier alternations are allowed) or more expressible (after powering with counting quantifiers).

preprint2013arXiv

Minimum Number of k-Cliques in Graphs with Bounded Independence Number

Erdos asked in 1962 about the value of f(n,k,l), the minimum number of k-cliques in a graph of order n and independence number less than l. The case (k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all large n) when (k,l) is (3,4), (3,5), (3,6), (3,7), (4,3), (5,3), (6,3), and (7,3). Independently, Das, Huang, Ma, Naves, and Sudakov did the cases (k,l)=(3,4) and (4,3).

preprint2013arXiv

On Possible Turan Densities

The Turán density π(H) of a family H of k-graphs is the limit as n tends to infinity of the maximum edge density of an H-free k-graph on n vertices. Let I^k consist of all possible Turán densities and let F^k be the set of Turán densities of finite k-graph families. Here we prove that F^k contains every density obtained from an arbitrary finite construction by optimally blowing it up and using recursion inside the specified set of parts. As an application, we show that F^k contains an irrational number for each k\ge 3. Also, we show that I^k has cardinality of the continuum. In particular, I^k is not equal to F^k.

preprint2013arXiv

Poset limits can be totally ordered

S.Janson [Poset limits and exchangeable random posets, Combinatorica 31 (2011), 529--563] defined limits of finite posets in parallel to the emerging theory of limits of dense graphs. We prove that each poset limit can be represented as a kernel on the unit interval with the standard order, thus answering an open question of Janson. We provide two proofs: real-analytic and combinatorial. The combinatorial proof is based on a Szemeredi-type Regularity Lemma for posets which may be of independent interest. Also, as a by-product of the analytic proof, we show that every atomless ordered probability space admits a measure-preserving and almost order-preserving map to the unit interval.

preprint2013arXiv

Quasirandom permutations are characterized by 4-point densities

For permutations P and T of lengths |P|\le|T|, let t(P,T) be the probability that the restriction of T to a random |P|-point set is (order) isomorphic to P. We show that every sequence \{T_j\} of permutations such that |T_j|\to\infty and t(P,T_j)\to 1/4! for every 4-point permutation P is quasirandom (that is, t(P,T_j)\to 1/|P|! for every P). This answers a question posed by Graham.

preprint2012arXiv

On Minimum Saturated Matrices

Motivated by the work of Anstee, Griggs, and Sali on forbidden submatrices and the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let F be a family of k-row matrices. A matrix M is called F-admissible if M contains no submatrix G\in F (as a row and column permutation of G). A matrix M without repeated columns is F-saturated if M is F-admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat(n,F) which is the minimum number of columns of an F-saturated matrix with n rows. We establish the estimate sat(n,F)=O(n^{k-1}) for any family F of k-row matrices and also compute the sat-function for a few small forbidden matrices.

preprint2010arXiv

An Analytic Approach to Stability

The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order $n$ can be made isomorphic by changing o(n^2) edges. Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erdos-Simonovits Stability Theorem. Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fractional versions are within a constant factor from each other, thus answering a question of Goldreich, Krivelevich, Newman, and Rozenberg.

preprint2010arXiv

Untangling planar graphs from a specified vertex position - Hard cases

Given a planar graph $G$ , we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $π$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $π$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))\sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $π$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.

preprint2009arXiv

Maximizing the number of q-colorings

Let P_G(q) denote the number of proper q-colorings of a graph G. This function, called the chromatic polynomial of G, was introduced by Birkhoff in 1912, who sought to attack the famous four-color problem by minimizing P_G(4) over all planar graphs G. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing P_G(q) over various families of graphs. In this paper, we study an old problem of Linial and Wilf, to find the graphs with n vertices and m edges which maximize the number of q-colorings. We provide the first approach which enables one to solve this problem for many nontrivial ranges of parameters. Using our machinery, we show that for each q >= 4 and sufficiently large m < κ_q n^2 where κ_q is approximately 1/(q log q), the extremal graphs are complete bipartite graphs minus the edges of a star, plus isolated vertices. Moreover, for q = 3, we establish the structure of optimal graphs for all large m <= n^2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989.

preprint2003arXiv

The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

We say that a first order formula A distinguishes a graph G from another graph G' if A is true on G and false on G'. Provided G and G' are non-isomorphic, let D(G,G') denote the minimal quantifier rank of a such formula. We prove that, if G and G' have the same order n, then D(G,G')\le(n+3)/2, which is tight up to an additive constant of 1. The analogous questions are considered for directed graphs (more generally, for arbitrary structures with maximum relation arity 2) and for k-uniform hypergraphs. Also, we study defining formulas, where we require that A distinguishes G from any other non-isomorphic G'.

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.

Oleg Pikhurko

Research overview

Is this your work?

30 publications

Rational codegree Turán density of hypergraphs

Disjoint isomorphic balanced clique subdivisions

Divisibility of Spheres with Measurable Pieces

On a question of Vera T. Sós about size forcing of graphons

Borel Combinatorics of Locally Finite Graphs

Measurable versions of Vizing's theorem

The exact minimum number of triangles in graphs of given order and size

Minimizing the number of 5-cycles in graphs with given edge-density

Kőnig's Line Coloring and Vizing's Theorems for Graphings

Measurable circle squaring

Supersaturation Problem for Color-Critical Graphs

Spherical sets avoiding a prescribed set of angles

The codegree threshold for 3-graphs with independent neighbourhoods

The maximal length of a gap between r-graph Turán densities

Asymptotic Structure of Graphs with the Minimum Number of Triangles

Coloring d-Embeddable k-Uniform Hypergraphs

Martin Gardner's minimum no-3-in-a-line problem

Measurable equidecompositions via combinatorics and group theory

Minimum number of monotone subsequences of length 4 in permutations

Monochromatic Clique Decompositions of Graphs

Logical complexity of graphs: a survey

Minimum Number of k-Cliques in Graphs with Bounded Independence Number

On Possible Turan Densities

Poset limits can be totally ordered

Quasirandom permutations are characterized by 4-point densities

On Minimum Saturated Matrices

An Analytic Approach to Stability

Untangling planar graphs from a specified vertex position - Hard cases

Maximizing the number of q-colorings

The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

See the researcher in context

Building this map preview