Source author record

Andras Gyarfas

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

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Large Cross-free sets in Steiner triple systems

A {\em cross-free} set of size $m$ in a Steiner triple system $(V,{\cal{B}})$ is three pairwise disjoint $m$ -element subsets $X_1,X_2,X_3\subset V$ such that no $B\in {\cal{B}}$ intersects all the three $X_i$ -s. We conjecture that for every admissible $n$ there is an STS $(n)$ with a cross-free set of size $\lfloor{n-3\over 3}\rfloor$ which if true, is best possible. We prove this conjecture for the case $n=18k+3$ , constructing an STS $(18k+3)$ containing a cross-free set of size $6k$ . We note that some of the $3$ -bichromatic STSs, constructed by Colbourn, Dinitz and Rosa, have cross-free sets of size close to $6k$ (but cannot have size exactly $6k$ ). The constructed STS $(18k+3)$ shows that equality is possible for $n=18k+3$ in the following result: in every $3$ -coloring of the blocks of any Steiner triple system STS $(n)$ there is a monochromatic connected component of size at least $\lceil{2n\over 3}\rceil+1$ (we conjecture that equality holds for every admissible $n$ ). The analogue problem can be asked for $r$ -colorings as well, if $r-1 \equiv 1,3 \mbox{ (mod 6)}$ and $r-1$ is a prime power, we show that the answer is the same as in case of complete graphs: in every $r$ -coloring of the blocks of any STS $(n)$ , there is a monochromatic connected component with at least ${n\over r-1}$ points, and this is sharp for infinitely many $n$ .

preprint2015arXiv

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of $2$ -edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every $2$ -edge-colored graph can be partitioned into at most $2α(G)$ monochromatic cycles, where $α(G)$ denotes the independence number of $G$ . Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from $o(|V(G)|)$ vertices, the vertex set of any $2$ -edge-colored graph $G$ with minimum degree at least $(1+\eps){3|V(G)|\over 4}$ can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $\overline{G}$ does not contain a fixed bipartite graph $H$ , we show that in every $2$ -edge-coloring of $G$ , $|V(G)|-c(H)$ vertices can be covered by two vertex disjoint paths of different colors, where $c(H)$ is a constant depending only on $H$ . In particular, we prove that $c(C_4)=1$ , which is best possible.

preprint2015arXiv

Ramsey number of a connected triangle matching

We determine the $2$ -color Ramsey number of a {\em connected} triangle matching $c(nK_3)$ which is any connected graph containing $n$ vertex disjoint triangles. We obtain that $R(c(nK_3),c(nK_3))=7n-2$ , somewhat larger than in the classical result of Burr, Erd\H os and Spencer for a triangle matching, $R(nK_3,nK_3)=5n$ . The motivation is to determine the Ramsey number $R(C_n^2,C_n^2)$ of the square of a cycle $C_n^2$ . We apply our Ramsey result for connected triangle matchings to show that the Ramsey number of an "almost" square of a cycle $C_n^{2,c}$ (a cycle of length $n$ in which all but at most a constant number $c$ of short diagonals are present) is asymptotic to $7n/3$ .

preprint2015arXiv

Red-blue clique partitions and (1-1)-transversals

Motivated by the problem of Gallai on $(1-1)$ -transversals of $2$ -intervals, it was proved by the authors in 1969 that if the edges of a complete graph $K$ are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced $C_4$ and $C_5$ then the vertices of $K$ can be partitioned into a red and a blue clique. Aharoni, Berger, Chudnovsky and Ziani recently strengthened this by showing that it is enough to assume that there is no induced monochromatic $C_4$ and there is no induced $C_5$ in {\em one of the colors}. Here this is strengthened further, it is enough to assume that there is no monochromatic induced $C_4$ and there is no $K_5$ on which both color classes induce a $C_5$ . We also answer a question of Kaiser and Rabinovich, giving an example of six $2$ -convex sets in the plane such that any three intersect but there is no $(1-1)$ -transversal for them.

preprint2015arXiv

Replacing the host K_n by n-chromatic graphs in Ramsey-type results

We extend two well-known results in Ramsey theory from from $K_n$ to arbitrary $n$ -chromatic graphs. The first is a note of Erd\H os and Rado stating that in every 2-coloring of the edges of $K_n$ there is a monochromatic tree on $n$ vertices. The second is the theorem of Cockayne and Lorimer stating that for positive integers satisfying $n_1=\max\{n_1,n_2,\dots,n_t\}$ and with $n=n_1+1+\sum_{i=1}^t (n_i-1)$ , the following holds. In every coloring of the edges of $K_n$ with colors $1,2\dots,t$ there is a monochromatic matching of size $n_i$ for some $i\in \{1,2,\dots,t\}$ .

preprint2015arXiv

Vertex covers by monochromatic pieces - A survey of results and problems

This survey is devoted to problems and results concerning covering the vertices of edge colored graphs or hypergraphs with monochromatic paths, cycles and other objects. It is an expanded version of the talk with the same title at the Seventh Cracow Conference on Graph Theory, held in Rytro in September 14-19, 2014.

preprint2013arXiv

Multicolor Ramsey numbers for triple systems

Given an $r$ -uniform hypergraph $H$ , the multicolor Ramsey number $r_k(H)$ is the minimum $n$ such that every $k$ -coloring of the edges of the complete $r$ -uniform hypergraph $K_n^r$ yields a monochromatic copy of $H$ . We investigate $r_k(H)$ when $k$ grows and $H$ is fixed. For nontrivial 3-uniform hypergraphs $H$ , the function $r_k(H)$ ranges from $\sqrt{6k}(1+o(1))$ to double exponential in $k$ . We observe that $r_k(H)$ is polynomial in $k$ when $H$ is $r$ -partite and at least single-exponential in $k$ otherwise. Erdős, Hajnal and Rado gave bounds for large cliques $K_s^r$ with $s\ge s_0(r)$ , showing its correct exponential tower growth. We give a proof for cliques of all sizes, $s>r$ , using a slight modification of the celebrated stepping-up lemma of Erdős and Hajnal. For 3-uniform hypergraphs, we give an infinite family with sub-double-exponential upper bound and show connections between graph and hypergraph Ramsey numbers. Specifically, we prove that $r_k(K_3)\le r_{4k}(K_4^3-e)\le r_{4k}(K_3)+1,$ where $K_4^3-e$ is obtained from $K_4^3$ by deleting an edge. We provide some other bounds, including single-exponential bounds for $F_5=\{abe,abd,cde\}$ as well as asymptotic or exact values of $r_k(H)$ when $H$ is the bow $\{abc,ade\}$ , kite $\{abc,abd\}$ , tight path $\{abc,bcd,cde\}$ or the windmill $\{abc,bde,cef,bce\}$ . We also determine many new "small" Ramsey numbers and show their relations to designs. For example, the lower bound for $r_6(kite)=8$ is demonstrated by decomposing the triples of $[7]$ into six partial STS (two of them are Fano planes).

preprint2012arXiv

Rainbow matchings and partial transversals of Latin squares

In this paper we consider properly edge-colored graphs, i.e. two edges with the same color cannot share an endpoint, so each color class is a matching. A matching is called \it rainbow \rm if its edges have different colors. The minimum degree of a graph is denoted by $δ(G)$ . We show that properly edge colored graphs $G$ with $|V(G)|\ge 4δ(G)-3$ have rainbow matchings of size $δ(G)$ , this gives the best known estimate to a recent question of Wang. Since one obviously needs at least $2δ(G)$ vertices to guarantee a rainbow matching of size $δ(G)$ , we investigate what happens when $|V(G)|\ge 2δ(G)$ . We show that any properly edge colored graph $G$ with $|V(G)|\ge 2δ$ contains a rainbow matching of size at least $δ- 2δ(G)^{2/3}$ . This result extends (with a weaker error term) the well-known result that a factorization of the complete bipartite graph $K_{n,n}$ has a rainbow matching of size $n-o(n)$ , or equivalently that every Latin square of order $n$ has a partial transversal of size $n-o(n)$ (an asymptotic version of the Ryser - Brualdi conjecture). In this direction we also show that every Latin square of order $n$ has a {\em cycle-free partial transversal} of size $n-o(n)$ .

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.

Andras Gyarfas

Research overview

Is this your work?

8 publications

Large Cross-free sets in Steiner triple systems

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

Ramsey number of a connected triangle matching

Red-blue clique partitions and (1-1)-transversals

Replacing the host K_n by n-chromatic graphs in Ramsey-type results

Vertex covers by monochromatic pieces - A survey of results and problems

Multicolor Ramsey numbers for triple systems

Rainbow matchings and partial transversals of Latin squares

See the researcher in context

Building this map preview