Search for: All records

In their classical paper, Erdős, Goodman and Pósa studied the representation of a graph with vertex set $[n]$ by a family of subsets $$S_1,\dots, S_n$$ with the property that $$\{i,j\}$$ is an edge if and only if $$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. 

Abstract Daisies are a special type of hypergraph introduced by Bollobá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)}\}$$. Bollobás, Leader and Malvenuto initiated the study of Turán type density problems for daisies. This paper deals with Ramsey numbers of daisies, which are natural generalisations 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. 

Abstract For a ‐uniform hypergraph we consider the parameter , the minimum size of a clique cover of the edge set of . We derive bounds on for belonging to various classes of hypergraphs. 

Abstract For any integer$$h\geqslant 2$$ $h⩾2$, a set of integers$$B=\{b_i\}_{i\in I}$$ $B={\left\{b_i\right\}}_{i\in I}$is a$$B_h$$ $B_h$-set if allh-sums$$b_{i_1}+\ldots +b_{i_h}$$ $b_{i_1}+\dots +b_{i_h}$with$$i_1<\ldots $i_1<\dots <i_h$are distinct. Answering a question of Alon and Erdős [2], for every$$h\geqslant 2$$ $h⩾2$we construct a set of integersXwhich is not a union of finitely many$$B_h$$ $B_h$-sets, yet any finite subset$$Y\subseteq X$$ $Y\subseteq X$contains an$$B_h$$ $B_h$-setZwith$$|Z|\geqslant \varepsilon |Y|$$ $\left|Z\right|⩾\epsilon \left|Y\right|$, where$$\varepsilon :=\varepsilon (h)$$ $\epsilon :=\epsilon \left(h\right)$. We also discuss questions related to a problem of Pisier about the existence of a setAwith similar properties when replacing$$B_h$$ $B_h$-sets by the requirement that all finite sums$$\sum _{j\in J}b_j$$ ${\sum }_{j\in J}{b}_j$are distinct. 

In this paper we make a partial progress on the following conjecture: for every $$\mu>0$$ and large enough $$n$$, every Steiner triple system $$S$$ on at least $$(1+\mu)n$$ vertices contains every hypertree $$T$$ on $$n$$ vertices. We prove that the conjecture holds if $$T$$ is a perfect $$d$$-ary hypertree. 

Abstract Let $$\mathrm{AP}_k=\{a,a+d,\ldots,a+(k-1)d\}$$ be an arithmetic progression. For $$\varepsilon>0$$ we call a set $$\mathrm{AP}_k(\varepsilon)=\{x_0,\ldots,x_{k-1}\}$$ an $$\varepsilon$$ -approximate arithmetic progression if for some a and d , $$|x_i-(a+id)|<\varepsilon d$$ holds for all $$i\in\{0,1\ldots,k-1\}$$ . Complementing earlier results of Dumitrescu (2011, J. Comput. Geom. 2 (1) 16–29), in this paper we study numerical aspects of Van der Waerden, Szemerédi and Furstenberg–Katznelson like results in which arithmetic progressions and their higher dimensional extensions are replaced by their $$\varepsilon$$ -approximation. 

Abstract A well‐known result of Ajtai Komlós, Pintz, Spencer, and Szemerédi (J. Combin. Theory Ser. A32(1982), 321–335) states that every ‐graph on vertices, with girth at least five, and average degree contains an independent set of size for some . 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 , how large of an independent set a ‐graph on vertices necessarily has when its maximum ‐degree . (The corresponding problem with respect to ‐degrees was solved by Kostochka, Mubayi, and Verstraëte (Random Struct. & Algorithms44(2014), 224–239).) In this paper we show that every ‐graph on vertices with contains an independent set of size , and under additional conditions, an independent set of size . The former assertion gives a new upper bound for the ‐degree Turán density of complete ‐graphs.