V. Taranchuk

activity

20162026

most citedA New Lower Bound for van der Waerden Numbers

8 citations · 9 across the 18 of their papers we have counts for

collaborators

20 papers

math.CO2026

$K_{2, t + 1}$ -free graphs containing an optimal number of $K_{t, t}$ 's

Vladislav Taranchuk

The generalized Turán number $e x (n, K_{t, t}, K_{2, t + 1})$ is the maximum number of copies of $K_{t, t}$ that a $K_{2, t + 1}$ -free graph on $n$ vertices can contain. Recently, Pohoa…

cs.IT2026

On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

Philipp Heering, Christian Kaspers, Vladislav Taranchuk

A function $F : F_{2}^{n} \to F_{2}^{m}$ is called $k$ th-order sum-free if the sum of its values over any $k$ -dimensional affine subspace of $F_{2}^{n}$ is non-…

math.CO2026

A note on the chromatic number of Kneser graphs on chambers of projective planes and incidence-free sets

Philipp Heering, Klaus Metsch, Vladislav Taranchuk +1

Let $D = (P, B)$ be a symmetric $(v, k, λ)$ -design and let $(X, Y)$ be an equinumerous incidence-free pair, with $X \subseteq P$ and $Y \subseteq B$ …

cs.IT2026

Recovery Models for Linear Batch Codes

Baran Düzgün, Henk D. L. Hollmann, Ago-Erik Riet +2

Various types of recovery algorithms for batch codes have been considered previously, including asynchronous recovery and recovery algorithms arising from Almost Affinely Disjoint…

math.CO2026

Chromatic Number of Grassmann Graphs and MRD codes

Jozefien D'haeseleer, Francesco Pavese, Paolo Santonastaso +1

In this paper we investigate the chromatic number of the Grassmann graphs and of their powers, denoted $J_{q} (n, m, t)$ . In this graph, the vertices correspond to the $m$ -dimensional s…

math.CO2025

Line-parallelisms of PG $(n, 2)$ from Preparata-like codes

Philipp Heering, Vladislav Taranchuk

Partitions of the binary linear Hamming code into Preparata-like codes are known to induce line-parallelisms of PG $(n, 2)$ . In this paper, we show that if $P$ is any Preparata-like…

math.CO2025

Examples of diameter-2 graphs with no triangle or $K_{2, t}$

Sean Eberhard, Vladislav Taranchuk, Craig Timmons

For each $t \geq 1$ let $W_{t}$ denote the class of graphs other than stars that have diameter $2$ and contain neither a triangle nor a $K_{2, t}$ . The famous Hoffman--Singleton Theore…

math.CO2025

On the Chromatic Number of Grassmann Graphs

Jozefien D'haeseleer, Vladislav Taranchuk

In this paper we study the chromatic number of the Grassmann graphs $J_{q} (n, m)$ . We show that $(1 n - m + 1)_{q} \leq χ (J_{q} (n, m)) \leq (1 n)_{q}$ , which is analogous to the…

math.CO2025

New constructions of unbalanced ${C_{4}, θ_{3, t}}$ -free bipartite graphs

Baran Düzgün, Ago-Erik Riet, Vladislav Taranchuk

In 1979, Erdős conjectured that if $m = O (n^{2/3})$ , then $e x (n, m, {C_{4}, C_{6}}) = O (n)$ . This conjecture was disproven by several papers and the current best-known bounds for th…

math.CO2024

A new lower bound for the multicolor Ramsey number $r_{k} (K_{2, t + 1})$

Vladislav Taranchuk

In this short note, we provide a new infinite family of $K_{2, t + 1}$ -free graphs for each prime power $t$ . Using these graphs, we show that it is possible to partition the edges of…

math.CO2024

Large line-free sets and their applications

Jakob Führer, Vladislav Taranchuk

In this paper, we construct explicit families of polynomials $P \in F_{q} [x_{1}, \dots, x_{n}]$ with large root sets which have restricted intersections with affine lines. We use…

math.CO2023

Achromatic colorings of polarity graphs

Vladislav Taranchuk, Craig Timmons

A complete partition of a graph $G$ is a partition of the vertex set such that there is at least one edge between any two parts. The largest $r$ such that $G$ has a complete partit…

math.CO2022

A simple proof for the lower bound of the girth of graphs $D (n, q)$

Vladislav Taranchuk

The components of the graphs $D (n, q)$ provide the best-known general lower bound for the number of edges in a graph with $n$ vertices and no cycles of length less than $g$ . In thi…

math.CO2022

On the eigenvalues of the graphs $D (5, q)$

Himanshu Gupta, Vladislav Taranchuk

Let $q = p^{e}$ , where $p$ is a prime and $e$ is a positive integer. The family of graphs $D (k, q)$ , defined for any positive integer $k$ and prime power $q$ , were introduced by Laze…

math.CO2021

A New Family of Algebraically Defined Graphs With Small Automorphism Group

Felix Lazebnik, Vladislav Taranchuk

Let $p$ be an odd prime, $q = p^{e}$ , $e \geq 1$ , and $F = F_{q}$ denote the finite field of $q$ elements. Let $f : F^{2} \to F$ and $g: \mathbb{F}^3\to \ma…

math.CO2021★ 1 cited

On the number of $k$ -gons in finite projective planes

Vladislav Taranchuk

Let $Π$ be a projective plane of order $n$ and $Γ_{Π}$ be its Levi graph (the point-line incidence graph). For fixed $k \geq 3$ , let $c_{2 k} (Γ_{Π})$ denote the number of $2 k$ -cycles in…

math.CO2018

The Anti-Ramsey Problem for the Sidon equation

Vladislav Taranchuk, Craig Timmons

For $n \geq k \geq 4$ , let $A R_{X + Y = Z + T}^{k} (n)$ be the maximum number of rainbow solutions to the Sidon equation $X + Y = Z + T$ over all $k$ -colorings $c : [n] \to [k]$ .…

math.CO2017

A Constructive Lower Bound on Szemerédi's Theorem

Vladislav Taranchuk

Let $r_{k} (n)$ denote the maximum cardinality of a set $A \subset {1, 2, \dots, n}$ such that $A$ does not contain a $k$ -term arithmetic progression. In this paper, we give a metho…

math.CO2017★ 8 cited

A New Lower Bound for van der Waerden Numbers

Thomas Blankenship, Jay Cummings, Vladislav Taranchuk

In this paper we prove a new recurrence relation on the van der Waerden numbers, $w (r, k)$ . In particular, if $p$ is a prime and $p \leq k$ then $w(r, k) > p \cdot \left(w\left(r - \…

math.CO2016

Pancyclicity when each cycle contains k chords

Vladislav Taranchuk

For integers $n \geq k \geq 2$ , let $c (n, k)$ be the minimum number of chords that must be added to a cycle of length $n$ so that the resulting graph has the property that for every…

K2,t+1​-free graphs containing an optimal number of Kt,t​'s

On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

A note on the chromatic number of Kneser graphs on chambers of projective planes and incidence-free sets

Recovery Models for Linear Batch Codes

Chromatic Number of Grassmann Graphs and MRD codes

Line-parallelisms of PG(n,2) from Preparata-like codes

Examples of diameter-2 graphs with no triangle or K2,t​

On the Chromatic Number of Grassmann Graphs

New constructions of unbalanced {C4​,θ3,t​}-free bipartite graphs

A new lower bound for the multicolor Ramsey number rk​(K2,t+1​)

Large line-free sets and their applications

Achromatic colorings of polarity graphs

A simple proof for the lower bound of the girth of graphs D(n,q)

On the eigenvalues of the graphs D(5,q)

A New Family of Algebraically Defined Graphs With Small Automorphism Group

On the number of k-gons in finite projective planes

The Anti-Ramsey Problem for the Sidon equation

A Constructive Lower Bound on Szemerédi's Theorem

A New Lower Bound for van der Waerden Numbers

Pancyclicity when each cycle contains k chords

$K_{2, t + 1}$ -free graphs containing an optimal number of $K_{t, t}$ 's

Line-parallelisms of PG $(n, 2)$ from Preparata-like codes

Examples of diameter-2 graphs with no triangle or $K_{2, t}$

New constructions of unbalanced ${C_{4}, θ_{3, t}}$ -free bipartite graphs

A new lower bound for the multicolor Ramsey number $r_{k} (K_{2, t + 1})$

A simple proof for the lower bound of the girth of graphs $D (n, q)$

On the eigenvalues of the graphs $D (5, q)$

On the number of $k$ -gons in finite projective planes