BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Joanna Polcyn appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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 \,.$$
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$.
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})$.
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.
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.
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.
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.
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\}$.
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$.
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\}$.
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.