J. Polcyn

activity

20152024

most citedOn Hamiltonian cycles in hypergraphs with dense link graphs

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

collaborators

Showing math.COShow all

20 papers · 1 filter

math.CO2024

Strong Brandt-Thomassé Theorems

Tomasz Łuczak, Joanna Polcyn, Christian Reiher

Solving a long standing conjecture of Erdős and Simonovits, Brandt and Thomassé proved that the chromatic number of each triangle-free graph $G$ such that $δ (G) > ∣ V (G) ∣/3$ is at mos…

math.CO2023

The next case of Andrásfai's conjecture

Tomasz Łuczak, Joanna Polcyn, Christian Reiher

Let $ex (n, s)$ denote the maximum number of edges in a triangle-free graph on $n$ vertices which contains no independent sets larger than $s$ . The behaviour of $\mathrm{ex}…

math.CO2022

On the restricted size Ramsey number for a pair of cycles

Tomasz Łuczak, Joanna Polcyn, Zahra Rahimi

For graphs $H_{1}, H_{2}$ by $r^{*} (H_{1}, H_{2})$ we denote the minimum number of edges in a graph $G$ on $r (H_{1}, H_{2})$ vertices such that $G \to (H_{1}, H_{2})$ . We show that for each pair of natur…

math.CO2022

Two disjoint cycles in digraphs

Mikołaj Lewandowski, Joanna Polcyn, Christian Reiher

Bermond and Thomassen conjectured that every digraph with minimum outdegree at least $2 k - 1$ contains $k$ vertex disjoint cycles. So far the conjecture was verified for $k \leq 3$ . He…

math.CO2020

Turán and Ramsey numbers for $3$ -uniform minimal paths of length $4$

Jie Han, Joanna Polcyn, Andrzej Ruciński

We determine Turán numbers for the family of 3-uniform minimal paths of length four \emph{for all $n$ }. We also establish the second and third order Turán numbers and use them to c…

math.CO2020★ 9 cited

On Hamiltonian cycles in hypergraphs with dense link graphs

Joanna Polcyn, Christian Reiher, Vojtěch Rödl +1

We show that every $k$ -uniform hypergraph on $n$ vertices whose minimum $(k - 2)$ -degree is at least $(5/9 + o (1)) n^{2} /2$ contains a Hamiltonian cycle. A construction due to Han and Zha…

math.CO2020★ 5 cited

Minimum pair degree condition for tight Hamiltonian cycles in $4$ -uniform hypergraphs

Joanna Polcyn, Christian Reiher, Vojtěch Rödl +3

We show that every 4-uniform hypergraph with $n$ vertices and minimum pair degree at least $(5/9 + o (1)) n^{2} /2$ contains a tight Hamiltonian cycle. This degree condition is asymptotic…

math.CO2020★ 1 cited

The Ramsey number of a long even cycle versus a star

Peter Allen, Tomasz Łuczak, Joanna Polcyn +1

We find the exact value of the Ramsey number $R (C_{2 ℓ}, K_{1, n})$ , when $ℓ$ and $n = O (ℓ^{10/9})$ are large. Our result is closely related to the behaviour of Turán number $e…

math.CO2020★ 4 cited

Andrásfai and Vega graphs in Ramsey-Turán theory

Tomasz Łuczak, Joanna Polcyn, Christian Reiher

Given positive integers $n \geq s$ , we let $ex (n, s)$ denote the maximum number of edges in a triangle-free graph $G$ on $n$ vertices with $α (G) \leq s$ . In the early sixties…

math.CO2020★ 5 cited

On the Ramsey-Turán density of triangles

Tomasz Łuczak, Joanna Polcyn, Christian Reiher

One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ edges. About half a cent…

math.CO2017★ 1 cited

A tale of stars and cliques

Tomasz Łuczak, Joanna Polcyn, Christian Reiher

We show that for an infinitely many natural numbers $k$ there are $k$ -uniform hypergraphs which admit a `rescaling phenomenon' as described in [9]. More precisely, let $\mathcal{A}…

math.CO2017★ 1 cited

The multipartite Ramsey number for the 3-path of length three

Tomasz Luczak, Joanna Polcyn

We study the Ramsey number for the 3-path of length three and $n$ colors and show that $R (P_{3}^{3}; n) \leq λ_{0} n + 7 n$ , for some explicit constant $λ_{0} = 1.97466 \dots$ .

math.CO2017★ 2 cited

Paths in hypergraphs: a rescaling phenomenon

Tomasz Luczak, Joanna Polcyn

Let $P_{ℓ}^{k}$ denote the loose $k$ -path of length $ℓ$ and let define $f_{ℓ}^{k} (n, m)$ as the minimum value of $Δ (H)$ over all $P_{ℓ}^{k}$ -free $k$ -graphs $H$ with $n$ vertices an…

math.CO2017

On multicolor Ramsey numbers for loose $k$ -paths of length three

Tomasz Łuczak, Joanna Polcyn, Andrzej Ruciński

We show that there exists an absolute constant $A$ such that for each $k \geq 2$ and every coloring of the edges of the complete $k$ -uniform hypergraph on $A r$ vertices with $r$ colo…

math.CO2016

On multicolor Ramsey number for 3-paths of length three

Tomasz Łuczak, Joanna Polcyn

We show that if we color the hyperedges of the complete $3$ -uniform complete graph on $2 n + 18 n + 1 + 2$ vertices with $n$ colors, then one of the color classes contains a loose p…

math.CO2016

A hierarchy of maximal intersecting triple systems

Joanna Polcyn, Andrzej Rucinski

We reach beyond the celebrated theorems of Erdős-Ko-Rado and Hilton-Milner, and, a recent theorem of Han-Kohayakawa, and determine all maximal intersecting triples systems. It turn…

math.CO2015

One more Turán number and Ramsey number for the loose 3-uniform path of length three

Joanna Polcyn

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a, b, c, d, e, f, g$ and 3 edges ${a, b, c}, {c, d, e},$ and ${e, f, g}$ . It is known that the $r$ -color Ramsey number for…

math.CO2015

Refined Turán numbers and Ramsey numbers for the loose 3-uniform path of length three

Joanna Polcyn, Andrzej Ruciński

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a, b, c, d, e, f, g$ and 3 edges ${a, b, c}, {c, d, e},$ and ${e, f, g}$ . It is known that the $r$ -color Ramsey number for…

math.CO2015

Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three

Eliza Jackowska, Joanna Polcyn, Andrzej Ruciński

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a, b, c, d, e, f, g$ and 3 edges ${a, b, c}, {c, d, e},$ and ${e, f, g}$ . It is known that the $r$ -colored Ramsey number f…

math.CO2015

Turán numbers for 3-uniform linear paths of length 3

Eliza Jackowska, Joanna Polcyn, Andrzej Ruciński

In this paper we confirm a conjecture of Füredi, Jiang, and Seiver, and determine an exact formula for the Turán number $e x_{3} (n; P_{3}^{3})$ of the 3-uniform linear path $P_{3}^{3}$ of len…

Strong Brandt-Thomassé Theorems

The next case of Andrásfai's conjecture

On the restricted size Ramsey number for a pair of cycles

Two disjoint cycles in digraphs

Turán and Ramsey numbers for 3-uniform minimal paths of length 4

On Hamiltonian cycles in hypergraphs with dense link graphs

Minimum pair degree condition for tight Hamiltonian cycles in 4-uniform hypergraphs

The Ramsey number of a long even cycle versus a star

Andrásfai and Vega graphs in Ramsey-Turán theory

On the Ramsey-Turán density of triangles

A tale of stars and cliques

The multipartite Ramsey number for the 3-path of length three

Paths in hypergraphs: a rescaling phenomenon

On multicolor Ramsey numbers for loose k-paths of length three

On multicolor Ramsey number for 3-paths of length three

A hierarchy of maximal intersecting triple systems

One more Turán number and Ramsey number for the loose 3-uniform path of length three

Refined Turán numbers and Ramsey numbers for the loose 3-uniform path of length three

Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three

Turán numbers for 3-uniform linear paths of length 3

Turán and Ramsey numbers for $3$ -uniform minimal paths of length $4$

Minimum pair degree condition for tight Hamiltonian cycles in $4$ -uniform hypergraphs

On multicolor Ramsey numbers for loose $k$ -paths of length three