Source author record

Joanna Polcyn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

11works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the restricted size Ramsey number for a pair of cycles

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 natural numbers $k,n$ , $k\le n$ , where $k$ is odd and $n$ is large enough, we have $r^*(C_n,C_k)=\lceil (n+1)(2n-1)/2\rceil \,.$

preprint2022arXiv

Two disjoint cycles in digraphs

Bermond and Thomassen conjectured that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex disjoint cycles. So far the conjecture was verified for $k\le 3$ . Here we generalise the question asking for all outdegree sequences which force $k$ vertex disjoint cycles and give the full answer for $k\le 2$ .

preprint2021arXiv

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

Given positive integers $n\ge s$ , we let ${\mathrm{ex}}(n,s)$ denote the maximum number of edges in a triangle-free graph $G$ on $n$ vertices with $α(G)\le s$ . In the early sixties Andrásfai conjectured that for $n/3<s<n/2$ the function ${\mathrm{ex}}(n, s)$ is piecewise quadratic with critical values at $s/n={k}/({3k-1})$ . We confirm that this is indeed the case whenever $s/n$ is slightly larger than a critical value, thus determining ${\mathrm{ex}}(n,s)$ for all $n$ and $s$ such that $s/n\in [{k}/({3k-1}), {k}/({3k-1})+γ_k]$ , where $γ_k=Θ(k^{-6})$ .

preprint2020arXiv

On Hamiltonian cycles in hypergraphs with dense link graphs

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 Zhao shows that this minimum degree condition is optimal. The same result was proved independently by Lang and Sahueza-Matamala.

preprint2020arXiv

On the Ramsey-Turán density of triangles

One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on $n$ vertices without independent sets of size $αn$ , where $2/5\le α< 1/2$ , are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai's work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs~ $G$ on $n$ vertices with $α(G)\ge 3n/8$ and state a conjecture on the structure of the densest triangle-free graphs $G$ with $α(G) > n/3$ . We remark that the case $α(G) \le n/3$ behaves differently, but due to the work of Brandt this situation is fairly well understood.

preprint2016arXiv

A hierarchy of maximal intersecting triple systems

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 turns out that for each $n\ge7$ there are exactly 15 pairwise non-isomorphic such systems (and 13 for $n=6$ ). We present our result in terms of a hierarchy of Turán numbers $\ex^{(s)}(n, M_2^{3})$, $s\ge1$ , where $M_2^{3}$ is a pair of disjoint triples. Moreover, owing to our unified approach, we provide short proofs of the above mentioned results (for triple systems only). The triangle $C_3$ is defined as $C_3=\{\{x_1,y_3,x_2\},\{x_1,y_2,x_3\}, \{x_2,y_1,x_3\}\}$ . Along the way we show that the largest intersecting triple system $H$ on $n\ge6$ vertices, which is not a star and is triangle-free, consists of $\max\{10,n\}$ triples. This facilitates our main proof's philosophy which is to assume that $H$ contains a copy of the triangle and analyze how the remaining edges of $H$ intersect that copy.

preprint2016arXiv

On multicolor Ramsey number for 3-paths of length three

We show that if we color the hyperedges of the complete $3$ -uniform complete graph on $2n+\sqrt{18n+1}+2$ vertices with $n$ colors, then one of the color classes contains a loose path of length three.

preprint2015arXiv

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

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 for $P$ is $R(P;r)=r+6$ for $r=2,3$ , and that $R(P;r)\le 3r$ for all $r\ge3$ . The latter result follows by a standard application of the Turán number $ex_3(n;P)$ , which was determined to be $\binom{n-1}2$ in our previous work. We have also shown that the full star is the only extremal 3-graph for $P$ . In this paper, we perform a subtle analysis of the Turán numbers for $P$ under some additional restrictions. Most importantly, we determine the largest number of edges in an $n$ -vertex $P$ -free 3-graph which is not a star. These Turán type results, in turn, allow us to confirm the formula $R(P;r)=r+6$ for $r\in\{4,5,6,7\}$ .

preprint2015arXiv

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

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 $P$ is $R(P;r)=r+6$ for $r\le 9$ . The proof of this result relies on a careful analysis of the Turán numbers for $P$ . In this paper, we refine this analysis further and compute the fifth order Turán number for $P$ , for all $n$ . Using this number for $n=16$ , we confirm the formula $R(P;10)=16$ .

preprint2015arXiv

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

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 $P$ is $R(P;r)=r+6$ for $r\le 7$ . The proof of this result relies on a careful analysis of the Turán numbers for $P$ . In this paper, we refine this analysis further and compute, for all $n$ , the third and fourth order Turán numbers for $P$ . With the help of the former, we confirm the formula $R(P;r)=r+6$ for $r\in\{8,9\}$ .

preprint2015arXiv

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

In this paper we confirm a conjecture of Füredi, Jiang, and Seiver, and determine an exact formula for the Turán number $ex_3(n; P_3^3)$ of the 3-uniform linear path $P^3_3$ of length 3, valid for all $n$ . It coincides with the analogous formula for the 3-uniform triangle $C^3_3$ , obtained earlier by Frankl and Füredi for $n\ge 75$ and Csákány and Kahn for all $n$ . In view of this coincidence, we also determine a `conditional' Turán number, defined as the maximum number of edges in a $P^3_3$ -free 3-uniform hypergraph on $n$ vertices which is \emph{not} $C^3_3$ -free.

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.

Joanna Polcyn

Research overview

Is this your work?

11 publications

On the restricted size Ramsey number for a pair of cycles

Two disjoint cycles in digraphs

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

On Hamiltonian cycles in hypergraphs with dense link graphs

On the Ramsey-Turán density of triangles

A hierarchy of maximal intersecting triple systems

On multicolor Ramsey number for 3-paths of length three

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

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

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

See the researcher in context

Building this map preview