Bartłomiej Kielak
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Bartłomiej Kielak has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Andrzej Grzesik
Faculty of Mathematics and Computer Science Jagiellonian University Kraków Poland
10 shared publications - Aliaksandra Novik
Section of Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
2 shared publications - Carla Groenland
Delft Institute of Applied Mathematics TU Delft The Netherlands
2 shared publications - Justyna Jaworska
Faculty of Mathematics and Computer Science Jagiellonian University Łojasiewicza 6 30-348 Kraków Poland
2 shared publications - Tomasz Ślusarczyk
Department of Mathematics Massachusetts Institute of Technology 02139 Cambridge MA USA
2 shared publications - Łukasz Bożyk
University of Warsaw
2 shared publications
Latest Publications
- 16 September 2026
- Published by Wiley in Journal of Graph Theory
Generalized Turán Problem for Directed Cycles
For integers , let denote the maximum number of directed cycles of length in any oriented graph on vertices which does not contain a directed cycle of length . We establish the order of magnitude of for every and and determine its value up to a lower error term when and is large enough. Additionally, we calculate the value of for some other specific pairs showing that a diverse class of extremal constructions can appear for small values of .
- 16 September 2026
- Published by Wiley in Journal of Graph Theory
Generalized Turán Problem for Directed Cycles
For integers , let denote the maximum number of directed cycles of length in any oriented graph on vertices which does not contain a directed cycle of length . We establish the order of magnitude of for every and and determine its value up to a lower error term when and is large enough. Additionally, we calculate the value of for some other specific pairs showing that a diverse class of extremal constructions can appear for small values of .
- 16 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (5) , 2907-2914
The Generalized Trifference Problem
We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. This problem is a special case of the perfect $k$ -hashing problem in theoretical computer science, corresponding to the $k=3$ case. For $m = 1$ , we get the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$ . By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. Moreover, we relate the trifference problem to the sunflower conjecture.
- 16 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (5) , 2907-2914
The Generalized Trifference Problem
We study the problem of finding the largest number $T(n, m)$ of ternary vectors of length $n$ such that for any three distinct vectors there are at least $m$ coordinates where they pairwise differ. This problem is a special case of the perfect $k$ -hashing problem in theoretical computer science, corresponding to the $k=3$ case. For $m = 1$ , we get the classical trifference problem which is wide open. We prove upper and lower bounds on $T(n, m)$ for various ranges of the parameter $m$ and determine the phase transition threshold on $m=m(n)$ where $T(n, m)$ jumps from constant to exponential in $n$ . By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. Moreover, we relate the trifference problem to the sunflower conjecture.
- 29 February 2024
- Published by Springer Nature in Annals of Combinatorics
- Vol. 28 (4) , 1303-1322
Turán Problems for Oriented Graphs
- 29 February 2024
- Published by Springer Nature in Annals of Combinatorics
- Vol. 28 (4) , 1303-1322
Turán Problems for Oriented Graphs
- Open Access
Quasirandom forcing orientations of cycles
An oriented graph $H$ is quasirandom-forcing if the limit (homomorphism) density of $H$ in a sequence of tournaments is $2^{-\|H\|}$ if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length $\ell$ is quasirandom-forcing if and only if $\ell\equiv 2$ mod $4$. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to $10$ are quasirandom-forcing.Open AccessQuasirandom forcing orientations of cycles
An oriented graph $H$ is quasirandom-forcing if the limit (homomorphism) density of $H$ in a sequence of tournaments is $2^{-\|H\|}$ if and only if the sequence is quasirandom. We study generalizations of the following result: the cyclic orientation of a cycle of length $\ell$ is quasirandom-forcing if and only if $\ell\equiv 2$ mod $4$. We show that no orientation of an odd cycle is quasirandom-forcing. In the case of even cycles, we find sufficient conditions on an orientation to be quasirandom-forcing, which we complement by identifying necessary conditions. Using our general results and spectral techniques used to obtain them, we classify which orientations of cycles of length up to $10$ are quasirandom-forcing. - Open Access
Turán problems for oriented graphs
A classical Turán problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph $H$ as a subgraph. It is well-known that the chromatic number of $H$ is the graph parameter which describes the asymptotic behavior of this maximum. Here, we consider an analogous problem for oriented graphs, where compressibility plays the role of the chromatic number. Since any oriented graph having a directed cycle is not contained in any transitive tournament, it makes sense to consider only acyclic oriented graphs as forbidden subgraphs. We provide basic properties of the compressibility, show that the compressibility of acyclic oriented graphs with out-degree at most 2 is polynomial with respect to the maximum length of a directed path, and that the same holds for a larger out-degree bound if the Erdős-Hajnal conjecture is true. Additionally, generalizing previous results on powers of paths and arbitrary orientations of cycles, we determine the compressibility of acyclic oriented graphs with a restricted structure.Open AccessTurán problems for oriented graphs
A classical Turán problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph $H$ as a subgraph. It is well-known that the chromatic number of $H$ is the graph parameter which describes the asymptotic behavior of this maximum. Here, we consider an analogous problem for oriented graphs, where compressibility plays the role of the chromatic number. Since any oriented graph having a directed cycle is not contained in any transitive tournament, it makes sense to consider only acyclic oriented graphs as forbidden subgraphs. We provide basic properties of the compressibility, show that the compressibility of acyclic oriented graphs with out-degree at most 2 is polynomial with respect to the maximum length of a directed path, and that the same holds for a larger out-degree bound if the Erdős-Hajnal conjecture is true. Additionally, generalizing previous results on powers of paths and arbitrary orientations of cycles, we determine the compressibility of acyclic oriented graphs with a restricted structure. - 8 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (7)
On the inducibility of oriented graphs on four vertices
- 8 March 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (7)
On the inducibility of oriented graphs on four vertices
- Open Access
On the inducibility of oriented graphs on four vertices
We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.
Open AccessOn the inducibility of oriented graphs on four vertices
We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.
- 9 September 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 99 (2) , 240-246
On the maximum number of odd cycles in graphs without smaller odd cycles
We prove that for each odd integer , every graph on vertices without odd cycles of length less than contains at most cycles of length . This extends the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by Erdős in 1984, and asymptotically determines the generalized Turán number for odd . In contrary to the previous results on the pentagon case, our proof is not computer-assisted.- 9 September 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 99 (2) , 240-246
On the maximum number of odd cycles in graphs without smaller odd cycles
We prove that for each odd integer , every graph on vertices without odd cycles of length less than contains at most cycles of length . This extends the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by Erdős in 1984, and asymptotically determines the generalized Turán number for odd . In contrary to the previous results on the pentagon case, our proof is not computer-assisted.- Open Access
On the maximum number of odd cycles in graphs without smaller odd cycles
We prove that for each odd integer $k \geq 7$, every graph on $n$ vertices without odd cycles of length less than $k$ contains at most $(n/k)^k$ cycles of length $k$. This generalizes the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by Erd\H{o}s in 1984, and asymptotically determines the generalized Tur\'an number $\mathrm{ex}(n,C_k,C_{k-2})$ for odd $k$. In contrary to the previous results on the pentagon case, our proof is not computer-assisted.Open AccessOn the maximum number of odd cycles in graphs without smaller odd cycles
We prove that for each odd integer $k \geq 7$, every graph on $n$ vertices without odd cycles of length less than $k$ contains at most $(n/k)^k$ cycles of length $k$. This generalizes the previous results on the maximum number of pentagons in triangle-free graphs, conjectured by Erd\H{o}s in 1984, and asymptotically determines the generalized Tur\'an number $\mathrm{ex}(n,C_k,C_{k-2})$ for odd $k$. In contrary to the previous results on the pentagon case, our proof is not computer-assisted. - Open Access
- 1 September 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (9)
Exact hyperplane covers for subsets of the hypercube
- 1 September 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (9)
Open AccessExact hyperplane covers for subsets of the hypercube