Recent zbMATH articles in MSC 05Dhttps://www.zbmath.org/atom/cc/05D2021-04-16T16:22:00+00:00WerkzeugStar-critical Ramsey numbers involving graphs with long suspended paths.https://www.zbmath.org/1456.051162021-04-16T16:22:00+00:00"Wang, Ye"https://www.zbmath.org/authors/?q=ai:wang.ye"Li, Yusheng"https://www.zbmath.org/authors/?q=ai:li.yusheng"Li, Yan"https://www.zbmath.org/authors/?q=ai:li.yan.5|li.yan.6|li.yan.2|li.yan.3|li.yan.10|li.yan.8|li.yan.4|li.yan.1|li.yan|li.yan.9|li.yan.7Summary: For graphs \(F\), \(G\) and \(H\), let \(F \to ( G , H )\) signify that any red/blue edge coloring of \(F\) contains a red \(G\) or a blue \(H\). The star-critical Ramsey number \(R_{\mathbb{S}} ( G , H ) = \max \{ n | K_r \setminus K_{1 , n} \to ( G , H ) \} \), where \(r = R ( G , H )\). In this note, it is shown that \(R_{\mathbb{S}} ( G , H_n ) = n + O ( 1 )\) for fixed \(G\) and \(H\) as \(n \to \infty \), where \(H_n\) is a graph of order \(n\) obtained from \(H\) by lengthening an edge to a path, each internal vertex of which has degree two. In addition, we determine the values of \(R_{\mathbb{S}} ( K_{1 , m} , P_n )\), \(R_{\mathbb{S}} ( K_{1 , m} , C_n )\), \(R_{\mathbb{S}} ( B_m , P_n )\) and \(R_{\mathbb{S}} ( F_m , P_n )\) for large \(n\).Turán and Ramsey numbers in linear triple systems.https://www.zbmath.org/1456.050862021-04-16T16:22:00+00:00"Gyárfás, András"https://www.zbmath.org/authors/?q=ai:gyarfas.andras"Sárközy, Gábor N."https://www.zbmath.org/authors/?q=ai:sarkozy.gabor-nSummary: In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex.
A famous result of \textit{I. Z. Ruzsa} and \textit{E. Szemerédi} [in: Combinatorics. Combinatorial colloquium held at Keszthely, Hungary, from 28 June to 3 July 1976. Vol. I and II. Amsterdam-Oxford-New York: North-Holland Publishing Company. 939--945 (1978; Zbl 0393.05031)] is that for any fixed \(c > 0\) and large enough \(n\) the following Turán-type theorem holds. If a linear triple system on \(n\) vertices has at least \(c n^2\) edges then it contains a triangle: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called \(s\)-configurations. The main tool is a generalization of the induced matching lemma from \(a b a\)-patterns to more general ones.
We slightly generalize \(s\)-configurations to extended \(s\)-configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any \(t\)-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail \(C_{15} \) (configuration with blocks 123, 345, 561 and 147), are \(t\)-Ramsey for any \(t \geq 1\). The most interesting one among them is the wicket, \( D_4\), formed by three rows and two columns of a \(3 \times 3\) point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.A remark on Hamilton cycles with few colors.https://www.zbmath.org/1456.050522021-04-16T16:22:00+00:00"Balla, Ior"https://www.zbmath.org/authors/?q=ai:balla.ior"Pokrovskiy, Alexey"https://www.zbmath.org/authors/?q=ai:pokrovskiy.alexey"Sudakov, Benny"https://www.zbmath.org/authors/?q=ai:sudakov.bennySummary: \textit{S. Akbari} et al. [Australas. J. Comb. 37, 33--42 (2007; Zbl 1130.05024)] conjectured that every proper edge-coloring of \(K_n\) with \(n\) colors contains a Hamilton cycle with \(\le O(\log n)\) colors. They proved that there is always a Hamilton cycle with \(\le 8\sqrt{n}\) colors. In this note we improve this bound to \(O(\log^3 n)\).Erdős-Ko-Rado type theorems for simplicial complexes via algebraic shifting.https://www.zbmath.org/1456.051672021-04-16T16:22:00+00:00"Kim, Younjin"https://www.zbmath.org/authors/?q=ai:kim.younjinSummary: \textit{P. Borg} [J. Lond. Math. Soc., II. Ser. 79, No. 1, 167--185 (2009; Zbl 1180.05118)] suggested a conjecture concerning the size of a \(t\)-intersecting \(k\)-uniform family of faces of an arbitrary simplicial complex. In this paper, we give a strengthening of Borg's conjecture for shifted simplicial complexes using algebraic shifting.Antichains of fixed diameter.https://www.zbmath.org/1456.051662021-04-16T16:22:00+00:00"Frankl, Peter"https://www.zbmath.org/authors/?q=ai:frankl.peterSummary: The main result of the paper is to prove for every \(r\ge 0\) and \(n>n_0(r)\) that every antichain on \(n\) vertices and consisting of more than \(\binom{n}{r}\) sets contains two members whose symmetric difference is at least \(2r+2\). The bound is best possible and all the extremal families are determined. For \(r\ge 3\) we show that \(n>6(r+1)^2\) is sufficient.A short proof of Bernoulli disjointness via the local lemma.https://www.zbmath.org/1456.370412021-04-16T16:22:00+00:00"Bernshteyn, Anton"https://www.zbmath.org/authors/?q=ai:bernshteyn.antonSummary: Recently, \textit{E. Glasner} and al. [Bernoulli disjointness, \url{https://arxiv.org/pdf/1901.03406.pdf}]
showed that if \(\Gamma\) is an infinite discrete group, then every minimal \(\Gamma\)-flow is disjoint from the Bernoulli shift \(2^\Gamma\). Their proof is somewhat involved; in particular, it invokes separate arguments for different classes of groups. In this note, we give a short and self-contained proof of their result using purely combinatorial methods applicable to all groups at once. Our proof relies on the Lovász Local Lemma, an important tool in probabilistic combinatorics that has recently found several applications in the study of dynamical systems.On diversity of certain \(t\)-intersecting families.https://www.zbmath.org/1456.051682021-04-16T16:22:00+00:00"Ku, Cheng Yeaw"https://www.zbmath.org/authors/?q=ai:ku.cheng-yeaw"Wong, Kok Bin"https://www.zbmath.org/authors/?q=ai:wong.kok-binSummary: Let \([n]=\{1,2,\dots, n\}\) and \(2^{[n]}\) be the set of all subsets of \([n]\). For a family \(\mathcal{F} \subseteq 2^{[n]}\), its diversity, denoted by \(\mathrm{div}(\mathcal{F})\), is defined to be \[
\mathrm{div}(\mathcal{F})=\min_{x\in [n]} \left\{ \left\vert \mathcal{F}(\overline x) \right\vert \right\},
\]
where \(\mathcal{F}(\overline x)=\left\{ F\in\mathcal{F} : x\notin \mathcal{F} \right\} \). Basically, \(\mathrm{div}(\mathcal{F})\) measures how far \(\mathcal{F}\) is from a trivial intersecting family, which is called a star. In this paper, we consider a generalization of diversity for \(t\)-intersecting family.Cross-intersecting families of vectors.https://www.zbmath.org/1456.051692021-04-16T16:22:00+00:00"Pach, János"https://www.zbmath.org/authors/?q=ai:pach.janos"Tardos, Gábor"https://www.zbmath.org/authors/?q=ai:tardos.gaborSummary: Given a sequence of positive integers \(p=(p_1,\dots ,p_n)\), let \(S_p\) denote the family of all sequences of positive integers \(x=(x_1,\ldots ,x_n)\) such that \(x_i\leq p_i\) for all \(i\). Two families of sequences (or vectors), \(A,B\subseteq S_p\), are said to be \(r\)-cross-intersecting if no matter how we select \(x\in A\) and \(y\in B\), there are at least \(r\) distinct indices \(i\) such that \(x_i=y_i\). We determine the maximum value of \(|A|\cdot |B|\) over all pairs of \(r\)-cross-intersecting families and characterize the extremal pairs for \(r\geq 1\), provided that \(\min p_i>r+1\). The case \(\min p_i\leq r+1\) is quite different. For this case, we have a conjecture, which we can verify under additional assumptions. Our results generalize and strengthen several previous results by \textit{C. Berge} [Lect. Notes Math. 411, 13--20 (1974; Zbl 0295.05130)], \textit{P. Frankl} [in: Handbook of combinatorics. Vol. 1--2. Amsterdam: Elsevier (North-Holland); Cambridge, MA: MIT Press. 1293--1329 (1995; Zbl 0844.05094)], \textit{P. Frankl} and \textit{Z. Fueredi} [SIAM J. Algebraic Discrete Methods 1, 376--381 (1980; Zbl 0506.05001)], \textit{M. L. Livingston} [J. Comb. Theory, Ser. A 26, 162--165 (1979; Zbl 0416.05001)], \textit{A. Moon} [ibid. 32, 386--390 (1982; Zbl 0483.05002)], and \textit{N. Tokushige} [Comb. Probab. Comput. 22, No. 4, 622--637 (2013; Zbl 1269.05108)], and answers a question of \textit{H. Zhang} [Electron. J. Comb. 20, No. 1, Research Paper P17, 8 p. (2013; Zbl 1267.05283)]. The special case \(r=1\) has also been settled recently by \textit{P. Borg} [``Cross-intersecting integer sequences'', Preprint, \url{arXiv:1212.6955}].
For the entire collection see [Zbl 1318.68008].Restricted intersecting families on simplicial complex.https://www.zbmath.org/1456.051852021-04-16T16:22:00+00:00"Wang, Larry X. W."https://www.zbmath.org/authors/?q=ai:wang.larry-x-wSummary: Chvátal's conjecture on the intersecting family of the faces of the simplicial complex is a long-standing problem in combinatorics. \textit{H. Snevily} [J. Comb. Theory, Ser. A 61, No. 1, 137--141 (1992; Zbl 0760.05087)] gave an affirmative answer to this conjecture for near-cone complex. \textit{R. Woodroofe} [J. Comb. Theory, Ser. A 118, No. 4, 1218--1227 (2011; Zbl 1231.05308)] gave Erdős-Ko-Rado type theorem for near-cone complex by using algebraic shift method. Motivated by these results, we concern with the restricted intersecting family for the simplicial complex. First, we give an upper bound for the cardinality of the restricted intersecting family of the faces of the simplicial complex. Furthermore, we prove that if \(\mathcal{L}=\{l_1,l_2,\dots,l_s\}\) is a set of \(s\) positive integers, suppose that \(\triangle\) is a near-cone simplicial complex with an apex vertex \(v\) and \(\mathcal{F}=\{F_1,\dots,F_m\}\) is a family of the faces of \(\triangle\) such that \(|F_i \cap F_j|\in\mathcal{L}\) for every \(1\leq i\neq j\leq m\), then
\[
m\leq\sum\limits_{i=-1}^{s-1}f_i(\mathrm{link}_\triangle(v)),
\]
which generalizes Snevily's two theorems. We also propose a conjecture that this upper bound holds for all simplicial complexes. Finally, applying these theorems to certain simplicial complex, we can deduce the upper bounds for the cardinalities of the restricted intersecting families of the independent set of the graph, the set partition, the \(r\)-separated sets and the King Arthur and his Knight Table.Conditions for a bigraph to be super-cyclic.https://www.zbmath.org/1456.050882021-04-16T16:22:00+00:00"Kostochka, Alexandr"https://www.zbmath.org/authors/?q=ai:kostochka.alexandr-v"Lavrov, Mikhail"https://www.zbmath.org/authors/?q=ai:lavrov.mikhail"Luo, Ruth"https://www.zbmath.org/authors/?q=ai:luo.ruth"Zirlin, Dara"https://www.zbmath.org/authors/?q=ai:zirlin.daraSummary: A hypergraph \(\mathcal H\) is super-pancyclic if for each \(A \subseteq V(\mathcal{H})\) with \(|A| \geqslant 3, \mathcal{H}\) contains a Berge cycle with base vertex set \(A\). We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient. In particular, they are sufficient for every hypergraph \(\mathcal{H}\) with \(\delta(\mathcal{H})\geqslant \max\{|V(\mathcal{H})|, \frac{|E(\mathcal H)|+10}{4}\} \).
We also consider super-cyclic bipartite graphs: \((X,Y)\)-bigraphs \(G\) such that for each \(A \subseteq X\) with \(|A| \geqslant 3, G\) has a cycle \(C_A\) such that \(V(C_A)\cap X=A\). Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.Ramsey numbers for line graphs.https://www.zbmath.org/1456.051132021-04-16T16:22:00+00:00"Abbasi, Huzaifa"https://www.zbmath.org/authors/?q=ai:abbasi.huzaifa"Basavaraju, Manu"https://www.zbmath.org/authors/?q=ai:basavaraju.manu"Gurushankar, Eeshwar"https://www.zbmath.org/authors/?q=ai:gurushankar.eeshwar"Jivani, Yash"https://www.zbmath.org/authors/?q=ai:jivani.yash"Srikanth, Deepak"https://www.zbmath.org/authors/?q=ai:srikanth.deepakSummary: Given a graph, the classical Ramsey number \(R(k,l)\) is the least number of vertices that need to be in the graph for the existence of a clique of size \(k\) or an independent set of size \(l\). Finding \(R(k,l)\) exactly has been a notoriously hard problem. Even \(R(k,3)\) has not been determined for all values of \(k\). Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free graphs. The question with respect to line graph \(L(G)\) is equivalent to the minimum number of edges the underlying graph \(G\) needs to have for the existence of a vertex with degree \(k\) or a matching of size \(l\). \textit{V. Chvátal} and \textit{D. Hanson} [J. Comb. Theory, Ser. B 20, 128--138 (1976; Zbl 0324.05119)] determined this exactly for line graphs of simple graphs. Later \textit{N. Balachandran} and \textit{N. Khare} [Discrete Math. 309, No. 12, 4176--4180 (2009; Zbl 1218.05120)] gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvátal and Hanson [loc. cit.]. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs.
For the entire collection see [Zbl 1435.68020].Lower bounds for multicolor Ramsey numbers.https://www.zbmath.org/1456.051142021-04-16T16:22:00+00:00"Conlon, David"https://www.zbmath.org/authors/?q=ai:conlon.david"Ferber, Asaf"https://www.zbmath.org/authors/?q=ai:ferber.asafSummary: We give an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two.Existence of similar point configurations in thin subsets of \(\mathbb{R}^d\).https://www.zbmath.org/1456.520202021-04-16T16:22:00+00:00"Greenleaf, Allan"https://www.zbmath.org/authors/?q=ai:greenleaf.allan"Iosevich, Alex"https://www.zbmath.org/authors/?q=ai:iosevich.alex"Mkrtchyan, Sevak"https://www.zbmath.org/authors/?q=ai:mkrtchyan.sevakSummary: We prove the existence of similar and multi-similar point configurations (or simplexes) in sets of fractional Hausdorff dimension in Euclidean space. Let \(d \ge 2\) and \(E \subset \mathbb{R}^d\) be a compact set. For \(k \ge 1\), define
\[
\Delta_k(E) = \left\{\left(|x^1 - x^2|, \ldots, |x^i - x^j|, \ldots, |x^k - x^{k+1}|\right) : \left\{x^i\right\}_{i = 1}^{k + 1} \subset E \right\} \subset \mathbb{R}^{k(k+1)/2},
\]
the \((k+1)\)-point configuration set of \(E\). For \(k \le d\), this is (up to permutations) the set of congruences of \((k+1)\)-point configurations in \(E\); for \(k > d\), it is the edge-length set of \((k + 1)\)-graphs whose vertices are in \(E\). Previous works by a number of authors have found values \(s_{k, d} < d\) so that if the Hausdorff dimension of \(E\) satisfies \(\dim_{\mathcal H}(E) > s_{k, d} \), then \(\Delta_k(E)\) has positive Lebesgue measure. In this paper we study more refined properties of \(\Delta_k(E)\), namely the existence of similar or multi-similar configurations. For \(r \in \mathbb{R}, r > 0\), let
\[
\Delta_k^r(E) := \{\mathbf{t}\in \Delta_k (E) : r \mathbf{t} \in \Delta_k (E)\} \subset \Delta_k (E).
\]
We show that if \(\dim_{\mathcal H}(E) > s_{k, d}\), for a natural measure \(\nu_k\) on \(\Delta_k(E)\), one has \(\nu_k \left(\delta^r_k(E)\right)\) all \(r \in \mathbb{R}_+\). Thus, in \(E\) there exist many pairs of \((k + 1)\)-point configurations which are similar by the scaling factor \(r\). We extend this to show the existence of multi-similar configurations of any multiplicity. These results can be viewed as variants and extensions, for compact thin sets, of theorems of Furstenberg, Katznelson and Weiss [7], Bourgain [2] and Ziegler [11] for sets of positive density in \(\mathbb{R}^d\).New bounds on the Ramsey number \(r ( I_m , L_n )\).https://www.zbmath.org/1456.051702021-04-16T16:22:00+00:00"Ihringer, Ferdinand"https://www.zbmath.org/authors/?q=ai:ihringer.ferdinand"Rajendraprasad, Deepak"https://www.zbmath.org/authors/?q=ai:rajendraprasad.deepak"Weinert, Thilo"https://www.zbmath.org/authors/?q=ai:weinert.thilo-vSummary: We investigate the Ramsey number \(r ( I_m , L_n )\) which is the smallest natural number \(k\) such that every oriented graph on \(k\) vertices contains either an independent set of size \(m\) or a transitive tournament on \(n\) vertices. Continuing research by \textit{J. A. Larson} and \textit{W. J. Mitchell} [Ann. Comb. 1, No. 3, 245--252 (1997; Zbl 0895.05043)] and earlier work by \textit{J. C. Bermond} [Discrete Math. 9, 313--321 (1974; Zbl 0288.05111)] we establish two new upper bounds for \(r ( I_m , L_3 )\) which are paramount in proving \(r ( I_4 , L_3 ) = 15 < 23 = r ( I_5 , L_3 )\) and \(r ( I_m , L_3 ) = \Theta ( m^2 \slash \log m )\), respectively. We furthermore elaborate on implications of the latter on upper bounds for \(r ( I_m , L_n )\).