Search

We establish the existence of generalised Sidon sets enjoying additional Ramsey-type properties, which are motivated by questions of Erd\H{o}s and Newman and of Alon and Erd\H{o}s., Comment: 10 pages

The $k$-representation number of a graph $G$ is the minimum cardinality of the system of vertex subsets with the property that every edge of $G$ is covered at least $k$ times while every non-edge is covered at most $(k-1)$ times. In particular, for $k=1$ this notion is equivalent to the clique number of a graph $G$. Extending results of Frieze and Reed, and Eaton and Grable, we study the $k$-representation number of $G(n,1/2)$. As a tool, we will prove a sharp concentration result counting the number of induced subgraphs of $G(n,1/2)$ with density $(\frac{1}{2}+\alpha)$. In Lemma 3.7, we will show that the number of such subgraphs is close to its expected value with probability $1-\exp(-n^C)$.

A set of points $S$ in Euclidean space $\mathbb{R}^d$ is called \textit{Ramsey} if any finite partition of $\mathbb{R}^{\infty}$ yields a monochromatic copy of $S$. While characterization of Ramsey set remains a major open problem in the area, a stronger ``density'' concept was considered in [J. Amer. Math. Soc. 3, 1--7, 1990]: If $S$ is a $d$-dimensional simplex, then for any $\mu>0$ there is an integer $d:=d(S,\mu)$ and finite configuration $X\subseteq \mathbb{R}^d$ such that any subconfiguration $Y\subseteq X$ with $|Y|\geq \mu |X|$ contains a copy of $S$. Complementing this, here we show the existence of $\mu:=\mu(S)$ and of an infinite configuration $X\subseteq \mathbb{R}^{\infty}$ with the property that any finite coloring of $X$ yields a monochromatic copy of $S$, yet for any finite set of points $Y\subseteq X$ contains a subset $Z\subseteq Y$ of size $|Z|\geq \mu |Y|$ without a copy of $S$., Comment: Comments are welcome

In their classical paper, Erd\H{o}s, Goodman and Posa studied the representation of a graph by vertex set $[n]$ with a family of subsets $S_1,\dots, S_n$ with the property that $\{i,j\}$ is an edge iff $S_i\cap S_j\neq \emptyset$. In this note, we consider a similar representation of bounded degree $r$-uniform hypergraphs and establish some bounds for a corresponding problem.

According to Ramsey theorem, for every $k$ and $n$, if $N$ is sufficiently large, then for every 2-coloring $\psi$ of $k$-element subsets of $[N]$ there exists a monochromatic set $S\subseteq[N]$ (a set such that all $k$-element subsets of $S$ have the same color given by $\psi$), $|S|=m$. The least such number is denoted by $R_k(m)$. Old results of Erd\H os, Hajnal and Rado~\cite{erdos-hajnal-rado} imply that $R_k(m)\leq {\rm tw}_{k}(c m)$, where ${\rm tw}_k(x)$ is the tower function defined by ${\rm tw}_1(x)=x$ and ${\rm tw}_{i+1}(x)=2^{{\rm tw}_i(x)}$. On the other hand, these authors also showed that if $N\leq {\rm tw}_{k-1}(c'm^2)$, then there exists a coloring~$\psi$ such that there is no monochromatic $S\subseteq[N]$, $|S|=m$. We are interested in the question what more one can say when $N$ is smaller than ${\rm tw}_{k-1}(m)$ and $m$ is only slightly larger than $k$. We will show that, for particular values of the parameters $k,m,N$, there are colorings such that on all subsets $S$, $|S|\geq m$, the number of $k$-subsets of one color is close to the number of $k$-subsets of the other color. In this abstract, for the sake of simplicity, we only state a special case of our main theorem. Theorem There exists $\epsilon>0$ and $k_0$ such that for every $k\geq k_0$, if $N< {\rm tw}_{\lfloor\sqrt k\rfloor}(2)$, then there exists a coloring $\gamma:{[N]\choose k}\to\{-1,1\}$ such that for every $S\subseteq[N]$, $|S|\geq k+\sqrt k$, the following holds true \[ \left|\sum\{\gamma(X)\ |\ X\in\mbox{${S\choose k}$}\}\right| \leq 2^{-\epsilon \sqrt k}\mbox{${|S|\choose k}$}. \]

We construct for every integer $k\geq 3$ and every real $\mu\in(0, \frac{k-1}{k})$ a set of integers $X=X(k, \mu)$ which, when coloured with finitely many colours, contains a monochromatic $k$-term arithmetic progression, whilst every finite $Y\subseteq X$ has a subset $Z\subseteq Y$ of size $|Z|\geq \mu |Y|$ that is free of arithmetic progressions of length $k$. This answers a question of Erd\H{o}s, Ne\v{s}et\v{r}il, and the second author. Moreover, we obtain an analogous multidimensional statement and a Hales-Jewett version of this result., Comment: 6 figures, revised according to referee reports

Given a hypergraph $F$ and a number of colours $r$, there exists a hypergraph $H$ of the same girth satisfying $H\longrightarrow (F)_r$. Moreover, for every linear hypergraph $F$ there exists a Ramsey hypergraph $H$ that locally looks like a forest of copies of $F$., Comment: 27 beautiful figures

Daisies are a special type of hypergraphs introduced by Bollob\'{a}s, Leader and Malvenuto. An $r$-daisy determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P:\: P\in M^{(r)}\}$. In [Combin. Probab. Comput. 20, no. 5, 743-747, 2011] the authors studied Tur\'{a}n type density problems for daisies. This paper deals with Ramsey numbers of Daisies, which are natural generalizations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of $r$-daisies and also for special cases where the size of the kernel is bounded., Comment: 14 pages

We show that $3$-uniform hypergraphs with the property that all vertices have a quasirandom link graph with density bigger than $1/3$ contain a clique on five vertices. This result is asymptotically best possible., Comment: second version addresses referee reports

For a $k$-uniform hypergraph $F$ we consider the parameter $\Theta(F)$, the minimum size of a clique cover of the of $F$. We derive bounds on $\Theta(F)$ for $F$ belonging to various classes of hypergraphs., Comment: 14 pages

A well-known result of Ajtai et al. from 1982 states that every $k$-graph $H$ on $n$ vertices, with girth at least five, and average degree $t^{k-1}$ contains an independent set of size $c n (\log t)^{1/(k-1)}/t$ for some $c>0$. In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3 and 4. Our work is motivated by a problem of Lo and Zhao, who asked for $k\ge 4$, how large of an independent set a $k$-graph $H$ on $n$ vertices necessarily has when its maximum $(k-2)$-degree $\Delta_{k-2}(H)\le dn$. (The corresponding problem with respect to $(k-1)$-degrees was solved by Kostochka, Mubayi, and Varstra\"ete [Random Structures & Algorithms 44, 224--239, 2014].) In this paper we show that every $k$-graph $H$ on $n$ vertices with $\Delta_{k-2}(H)\le dn$ contains an independent set of size $c (\frac nd \log\log \frac nd)^{1/(k-1)}$, and under additional conditions, an independent set of size $c (\frac nd \log \frac nd)^{1/(k-1)}$. The former assertion gives a new upper bound for the $(k-2)$-degree Tur\'an density of complete $k$-graphs., Comment: To appear in Random Structures & Algorithms

The aim of this note is to give a simplified proof of the induced version of the Ramsey theorem for vector spaces first proved by H. J. Pr\"{o}mel., Comment: Comments are welcome