Source author record

Stanisław Radziszowski

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Information Theory math.IT

Catalog footprint

Research overview

7works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Zarankiewicz Numbers and Bipartite Ramsey Numbers

The Zarankiewicz number $z(b;s)$ is the maximum size of a subgraph of $K_{b,b}$ which does not contain $K_{s,s}$ as a subgraph. The two-color bipartite Ramsey number $b(s,t)$ is the smallest integer $b$ such that any coloring of the edges of $K_{b,b}$ with two colors contains a $K_{s,s}$ in the first color or a $K_{t,t}$ in the second color. In this work, we design and exploit a computational method for bounding and computing Zarankiewicz numbers. Using it, we obtain several new values and bounds on $z(b;s)$ for $3 \le s \le 6$ . Our approach and new knowledge about $z(b;s)$ permit us to improve some of the results on bipartite Ramsey numbers obtained by Goddard, Henning and Oellermann in 2000. In particular, we compute the smallest previously unknown bipartite Ramsey number, $b(2,5)=17$ . Moreover, we prove that up to isomorphism there exists a unique $2$ -coloring which witnesses the lower bound $16<b(2,5)$ . We also find tight bounds on $b(2,2,3)$ , $17 \le b(2,2,3) \le 18$ , which currently is the smallest open case for multicolor bipartite Ramsey numbers.

preprint2015arXiv

A step forwards on the Erdős-Sós problem concerning the Ramsey numbers $R(3,k)$

Let $Δ_s=R(K_3,K_s)-R(K_3,K_{s-1})$ , where $R(G,H)$ is the Ramsey number of graphs $G$ and $H$ defined as the smallest $n$ such that any edge coloring of $K_n$ with two colors contains $G$ in the first color or $H$ in the second color. In 1980, Erdős and Sós posed some questions about the growth of $Δ_s$ . The best known concrete bounds on $Δ_s$ are $3 \le Δ_s \le s$ , and they have not improved since the stating of the problem. In this paper we present some constructions, which imply in particular that $R(K_3,K_s) \ge R(K_3,K_{s-1}-e) + 4$ . This does not improve the lower bound of 3 on $Δ_s$ , but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving $Δ_s$ , including the following: for some constant $d$ and all $s$ it holds that $Δ_s - Δ_{s+1} \leq d$ . We also prove that if the latter is true, then $\lim_{s \rightarrow \infty} Δ_s/s=0$ .

preprint2014arXiv

On bipartization of cubic graphs by removal of an independent set

We study a new problem for cubic graphs: bipartization of a cubic graph $Q$ by deleting sufficiently large independent set $I$ . It can be expressed as follows: \emph{Given a connected $n$ -vertex tripartite cubic graph $Q=(V,E)$ with independence number $α(Q)$ , does $Q$ contain an independent set $I$ of size $k$ such that $Q-I$ is bipartite?} We are interested for which value of $k$ the answer to this question is affirmative. We prove constructively that if $α(Q) \geq 4n/10$ , then the answer is positive for each $k$ fulfilling $\lfloor (n-α(Q))/2 \rfloor \leq k \leq α(Q)$ . It remains an open question if a similar construction is possible for cubic graphs with $α(Q)<4n/10$ . Next, we show that this problem with $α(Q)\geq 4n/10$ and $k$ fulfilling inequalities $\lfloor n/3 \rfloor \leq k \leq α(Q)$ can be related to semi-equitable graph 3-coloring, where one color class is of size $k$ , and the subgraph induced by the remaining vertices is equitably 2-colored. This means that $Q$ has a coloring of type $(k, \lceil(n-k)/2\rceil, \lfloor (n-k)/2 \rfloor)$ .

preprint2013arXiv

Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs

In this note we study Shannon capacity of channels in the context of classical Ramsey numbers. We overview some of the results on capacity of noisy channels modelled by graphs, and how some constructions may contribute to our knowledge of this capacity. We present an improvement to the constructions by Abbott and Song and thus establish new lower bounds for a special type of multicolor Ramsey numbers. We prove that our construction implies that the supremum of the Shannon capacity over all graphs with independence number 2 cannot be achieved by any finite graph power. This can be generalized to graphs with any bounded independence number.

preprint2013arXiv

Computation of the Ramsey Numbers $R(C_4,K_9)$ and $R(C_4,K_{10})$

The Ramsey number $R(C_4,K_m)$ is the smallest $n$ such that any graph on $n$ vertices contains a cycle of length four or an independent set of order $m$ . With the help of computer algorithms we obtain the exact values of the Ramsey numbers $R(C_4,K_9)=30$ and $R(C_4,K_{10})=36$ . New bounds for the next two open cases are also presented.

preprint2013arXiv

Use of MAX-CUT for Ramsey Arrowing of Triangles

In 1967, Erdős and Hajnal asked the question: Does there exist a $K_4$ -free graph that is not the union of two triangle-free graphs? Finding such a graph involves solving a special case of the classical Ramsey arrowing operation. Folkman proved the existence of these graphs in 1970, and they are now called Folkman graphs. Erdős offered \$100 for deciding if one exists with less than $10^{10}$ vertices. This problem remained open until 1988 when Spencer, in a seminal paper using probabilistic techniques, proved the existence of a Folkman graph of order $3\times 10^9$ (after an erratum), without explicitly constructing it. In 2008, Dudek and Rödl developed a strategy to construct new Folkman graphs by approximating the maximum cut of a related graph, and used it to improve the upper bound to 941. We improve this bound first to 860 using their approximation technique and then further to 786 with the MAX-CUT semidefinite programming relaxation as used in the Goemans-Williamson algorithm.

preprint2005arXiv

Computation of the Ramsey Number $R(W_5,K_5)$

We determine the value of the Ramsey number $R(W_5,K_5)$ to be 27, where $W_5 = K_1 + C_4$ is the 4-spoked wheel of order 5. This solves one of the four remaining open cases in the tables given in 1989 by George R. T. Hendry, which included the Ramsey numbers $R(G,H)$ for all pairs of graphs $G$ and $H$ having five vertices, except seven entries. In addition, we show that there exists a unique up to isomorphism critical Ramsey graph for $W_5$ versus $K_5$ . Our results are based on computer algorithms.

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.

Stanisław Radziszowski

Research overview

Is this your work?

7 publications

Zarankiewicz Numbers and Bipartite Ramsey Numbers

A step forwards on the Erdős-Sós problem concerning the Ramsey numbers $R(3,k)$

On bipartization of cubic graphs by removal of an independent set

Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs

Computation of the Ramsey Numbers $R(C_4,K_9)$ and $R(C_4,K_{10})$

Use of MAX-CUT for Ramsey Arrowing of Triangles

Computation of the Ramsey Number $R(W_5,K_5)$

See the researcher in context

Building this map preview

Stanisław Radziszowski

Research overview

Is this your work?

7 publications

Zarankiewicz Numbers and Bipartite Ramsey Numbers

A step forwards on the Erdős-Sós problem concerning the Ramsey numbers R(3,k)R(3,k)R(3,k)

On bipartization of cubic graphs by removal of an independent set

Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs

Computation of the Ramsey Numbers R(C4,K9)R(C_4,K_9)R(C4​,K9​) and R(C4,K10)R(C_4,K_{10})R(C4​,K10​)

Use of MAX-CUT for Ramsey Arrowing of Triangles

Computation of the Ramsey Number R(W5,K5)R(W_5,K_5)R(W5​,K5​)

See the researcher in context

Building this map preview

A step forwards on the Erdős-Sós problem concerning the Ramsey numbers $R(3,k)$

Computation of the Ramsey Numbers $R(C_4,K_9)$ and $R(C_4,K_{10})$

Computation of the Ramsey Number $R(W_5,K_5)$