Sergey Bereg

We study small off-diagonal Ramsey numbers involving wheel graphs. Following Radziszowski’s convention, we write $W_n=K_1+C_{n-1}$ for the wheel on n vertices. A lower bound for $R(W_m,W_n)$ is certified by a graph G such that G is $W_m$-free and $\overline{G}$ is $W_n$-free. We conduct computational experiments using several complementary search techniques, including partial Ramsey colorings and local search procedures. The computations exploit the structure of wheels: G contains $W_n$ if and only if some vertex neighborhood contains a cycle $C_{n-1}$. We report new lower-bound constructions for three off-diagonal wheel Ramsey numbers and provide the corresponding Ramsey graphs as explicit certificates.

We develop algorithms for computing permutation polynomials (PPs) using normalization, so-called F-maps and G-maps, and the Hermite criterion. This allows for a more efficient computation of PPs for larger degrees and for larger finite fields. We use this to improve some lower bounds for $M(n,D)$, the maximum number of permutations on n symbols with a pairwise Hamming distance of D.

We improve on known upper bounds for the size of permutation arrays under the Chebyshev metric, defined as follows. The Chebyshev distance between permutations $\pi$ and $\sigma$ on the symbols $\{1,2,\dots ,n\}$, denoted by $d(\pi ,\sigma )$, is $max\left\{\right|{\pi }_i-{\sigma }_i\left|\right|1\le i\le n\}$. For an array A (set) of such permutations, the Chebyshev distance of A, denoted by $d\left(A\right)$, is $min\left\{d\right(\pi ,\sigma \left)\right|\pi ,\sigma \in A,\pi \ne \sigma \}$. An array A of such permutations with $d\left(A\right)=d$ will be called an $(n,d)$-PA. Let $P(n,d)$ denote the maximum size of any $(n,d)$-PA. The function $P(n,d)$ has been the subject of previous research. In this paper, we consider strings on the symbols $\{0,1,2\}$, with the 0’s representing low symbols and the 2’s high symbols for the function $P(n,d)$. An array A of such strings of length n is separable if for any two strings in A, there is a position $1\le i\le n$ such that the $i^{th}$ symbol in one string is 0 and the $i^{th}$ symbol in the other is a 2. The maximum size of a separable array of strings of length n, with a occurrences of the symbol 0 and b occurrences of the symbol 2, is denoted by $R(n;a,b)$. We show that $R(n;k,k)$ is an upper bound for $P(n,n-k)$ when $k\le {\displaystyle \frac{n}{2}}$. We derive upper bounds for $R(n;a,b)$ by various recursive and combinatorial methods, from which follow upper bounds for the Chebyshev function $P(n,d)$, which improve upon previous such upper bounds in the literature.

In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set $P$ of $2n$ points in the plane, and two sites $c_1$ and $c_2$, compute two $n$-stars $S_1$ and $S_2$ centered at $c_1$ and $c_2$ respectively such that the maximum weight of $S_1$ and $S_2$ is minimized. This problem is strongly NP-hard by a reduction from Equal-size Set-Partition with Rationals. Then we consider two variations of the Two-Squirrel problem, namely the Two-MST and Two-TSP problem, which are both NP-hard. The NP-hardness for the latter is obvious while the former needs a non-trivial reduction from Equal-size Set-Partition with Rationals. In terms of approximation algorithms, for Two-MST and Two-TSP we give factor 3.6402 and $4+\varepsilon$ approximations respectively. Finally, we also show some interesting polynomial-time solvable cases for Two-MST.