ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 18 (2020) 273-280 https://doi.org/10.26493/1855-3974.1957.a0f (Also available at http://amc-journal.eu) On the general position problem on Kneser graphs* * Balazs Patkost © Alfred Renyi Institute of Mathematics, Budapest, H-1364, Hungary, and Moscow Institute of Physics and Technology Received 22 March 2019, accepted 9 March 2020, published online 20 October 2020 Abstract In a graph G, a geodesic between two vertices x and y is a shortest path connecting x to y. A subset S of the vertices of G is in general position if no vertex of S lies on any geodesic between two other vertices of S. The size of a largest set of vertices in general position is the general position number that we denote by gp(G). Recently, Ghorbani et al. proved that for any k if n > k3 - k2 + 2k - 2, then gp(Knn,k) = (n-i), where Knn,k denotes the Kneser graph. We improve on their result and show that the same conclusion holds for n > 2.5k - 0.5 and this bound is best possible. Our main tools are a result on cross-intersecting families and a slight generalization of Bollobas's inequality on intersecting set pair systems. Keywords: General position problem, Kneser graphs, intersection theorems. Math. Subj. Class. (2020): 05D05, 05C35 1 Introduction A recently studied extremal problem [4, 6, 12] in graph theory is the following. In a graph G, a geodesic between two vertices x and y is a shortest path connecting x to y. We say that a subset S of the vertices of G is in general position if no vertex of S lies on any geodesic between two other vertices of S. The size of a largest set of vertices in general position *The author would like to thank Sandi KlavZar and Gregor Rus for pointing out that sets of the star are not in general position if n < 2.5k — 0.5. This was also pointed out later by both referees whom I thank for their thorough reading. I would like to thank Mate Vizer for showing me the relation of the families considered in the paper to qualitative independent partitions and Gabor Simonyi for providing me a short introduction to this topic. t Research supported by the National Research, Development and Innovation Office - NKFIH under the grants SNN 129364 andFK 132060. The author acknowledges the financial support from the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926 E-mail address: patkos@renyi.hu (Balazs Patkos) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 274 Ars Math. Contemp. 18 (2020) 187-210 is the general position number which we denote by gp(G). Our graph of interest in this paper is the Kneser graph Knnjk whose vertex is , the set of all k-element subsets of the set [n] = {1,2,... ,n} and two k-subsets S and T are joined by an edge if and only if S n T = 0. Ghorbani et al. [ ] determined gp(Knn,2) and gp(Knn,3) for all n and showed that for any fixed k if n is large enough, then gp (Kn) = (n-{) holds. Theorem 1.1 ([10]). Let n,k > 2 be integers with n > 3k — 1. If for all t, where 2 < t < k, the inequality k^-^ +1 < fn- Je holds, then gp(Knn,k) = in- 1 e. For fixed k and t = 2 the above inequality is satisfied when n > k3 — k2 + 2k — 1 holds. We improve on this and the main result of this note is the following. Theorem 1.2. If n, k > 4 are integers with n > 2k + 1, then gp(Knn,n) < (n-{) holds. Moreover, if n > 2.5k — 0.5, then we have gp (Knn,n) = (n- 1 ), while if 2k +1 < n < 2.5k — 0.5, then gp(Knn,k) < (n-J ) holds. The threshold n > 2.5k — 0.5 comes from the fact that diam(Knn n) < 3 holds if and only if this inequality is satisfied. The proof of Theorem 1.1 uses the following general result of Anand et al. [2] that characterizes vertex subsets in general position. Theorem 1.3 ([2]). If G is a connected graph, then a subset S of the vertices of G is in general position if and only if all the components S1, S2,..., Sh of G[S] are cliques in G and • for any 1 < i < j < h and si, si G Si, sj, sj G Sj we have d(si, sj) = d(s'i, sj) =: d(Si, Sj) (where d(x, y) denotes the distance of x and y in G), • d(S', Sj) = d(S', St) + d(Sh Sj) for any 1 < i,j,l < h. In Kneser graphs a clique corresponds to a family F C ([n^ of pairwise disjoint sets. There is no edge between different components of any general position set S. It follows that if F1, F2,..., Fh correspond to the components of G[S], then for any F' G F' and Fj G Fj with i = j we have F' n Fj = 0. Families with this property are called cross-intersecting. So the upper bound in Theorem 1.2 will follow from the next result unless n = 2k +1 in which case we will need some further reasonings. Theorem 1.4. Let n > 2k + 2, k > 4 and let F1, F2,..., Fh C f^ such that • F' n Fj = 0 for all 1 < i < j < h, • F' n F/ = 0 for all pairs of distinct sets F', F' G F' for any i = 1,2,... ,h, • Fi n Fj = 0 for any 1 < i < j < j and any Fi G Fi, Fj G Fj hold. Then we haveYlh= 1 |F'| < (n- 1 ). Note that the first condition cannot be omitted as otherwise we could repeat some families that consist of a single set. The remainder of the paper is organized as follows: Section 2 contains the proof of Theorem 1.4 and in Section 3 we list some open problems along with some remarks. B. Patkos: On the general position problem on Kneser graphs 275 2 Proofs Proof of Theorem 1.4. Let F1, F2,..., Fh C ([k') satisfy the conditions of the theorem. As the F;'s are families of pairwise disjoint sets, each of them are of size at most n/k and we may assume that |F^ < |F2| < • • • < |Fh| =: t < n/k. If t =1, then F = Uh=1Fj form an intersecting family and therefore by the celebrated theorem of Erdos, Ko and Rado [5] we have £ti |F;| = h < ("-1). Suppose next that t > 2 holds. Then we claim h < ("-) - (n---1) + 1. Indeed, let us fix one set F; from each F; for i = 1,2,..., h - 1 and two sets Fh, F^ e Fh. Hence if • | n?-1 Fj| > 2, then h - 1 < (k-2) < (k- 1 ) - ("-Y), ■,h-i. • nh=i F; consists of a single element x, then either Fh or F'h cannot contain x and as all Fj's meet both Fh and Fh we must have h - 1 < (k- 1 ) - ("—l), • n^T^Fj = 0, then {F1, F2,..., Fh- 1, Fh} is intersecting with no common elements, and a result of Hilton and Milner [ ] states that families with this property can have size at most ("- 1 ) - ("--11 ) + 1 so we oMain h < ("- 1 ) - ("--11 ) + L Let m; denote the number of j's such that |Fj | > i holds. Then clearly we have h t ^ |F;| = h + ^ mj < h +(J - ^ m2. (2.1) i=1 j=2 To bound m2 we apply Bollobas's famous inequality [ ] that states that if {(A1, B1)}j=1 are pairs of disjoint sets such that for any 1 < i = j < l we have A; n Bj = 0, then Y^i =1 /|Ail+|Bih < 1 holds. For any 1 < i < m2 we can pick two sets F;, G; e Fh-m2+i. ( * ) Then we can define 2m2 pairs {(Aj, Bj)}2mi such that for 1 < j < m2 we have Aj = Fj, Bj = Gj and A2m2-j = Gj, B2m2-j = Fj. As the F;'s are cross-intersecting families of disjoint sets, therefore the pairs {(Aj, Bj)}2m1 satisfy the conditions of Bollobas's inequality and we obtain (m) < 1 and thus m2 < 2 (2k) = Ck-1). Putting together (2.1) and the bounds on h and m2 we obtain A, , / n - 1\ /n - k - 1\ n - k /2k - 1 S|Fi'< (k - J-(k-1 )+1+—U- Therefore it is enough to prove (n-k-1) > (^tk-L1). Observe that (n-k) , i,i "-k + 1 (2k-1) U-J n - k >n - k + 1 —k—U-J i"-k-1) n - 2k + 1" n - k . k 1 k k1 therefore if (n0--1-1) > (2kk_r11) holds for some no, then (n---1) > (2kk_r11) holds for n > n0. Putting n0 = 3k + 2 the above inequality is equivalent to k-2 k-2 k ^ (2k +1 - i) > (2k + 2) ^ (2k - 1 - i) ;=o i=o 276 Ars Math. Contemp. 18 (2020) 187-210 which simpifies to k(2k + 1)2k > (2k + 2)(k + 2)(k + 1). This holds for k > 5 and a similar calculation shows that if k = 4, then the desired inequality holds if n > 17 = 4k +1. In all missing cases, except for k = 4, n = 16, we have n < 4k, therefore we have mj = 0 for all j > 4. So for the remaining pairs n and k, we need to strengthen our bound on m2 + m3. We will need the following lemma, a slight generalization of Bollobas's result. Lemma 2.1. Let {Ai,Bi|°L1 and {Aj, Bj, Cj }p=a+1 be pairs and triples of pairwise disjoint sets such that for any 1 < i < j < a + $ we have Xj n Yj = 0 where X and Y can be any of A, B and C. Then the following inequality holds: a+P E V Ai ) + P E j=i /\Aa + j \ + \Ca+j A |A„+j | ) + ( \Ba+j \ + \Ca+j \ ^a + j \ + \Ba + j \ + \Ca+j \ Aa+j \ ) ( \ A, a + j \ + \ Ba+j \ + \ Ca + j \ \ Ba+j \ 1. 2 2 2 a+3 2 2 Proof. Let us define M to be |J°=1(Ai U Bj) U [jlp=1(Aa+j U Ba+j U Ca+j) and let us write |M| = m. Just as before, let us introduce a family {Si, Tj}2=i1+P) of disjoint pairs as Sj = Aj= Bj and S2(a+p}-j = Bj,T2(a+p)-j = Aj for all 1 < i,j < a + We count the pairs (n, j) such that n is a permutation of the elements of M and 1 < j < 2(a + $) with all elements of Sj preceding all elements of Tj in n that is max{nj-1(s) : s G Sj} < min{n-1(t) : t G Tj}. We denote this by Sj 3(2fcfc) for k > 3, the left hand side of the above equation is greater than 2(m(22__m3) + ^ = 2(m(22++)m3). Therefore we obtain m2 + m3 < 1 (2kk) = (2fcfc__11). So for n < 4k we have the bound , / n - 1\ /n - k - 1\ /2k - 1\ Y|Fi|< h + m2 + m3 < (k - J -( k -1 J+1+U-lj (2.3) Suppose first that n > 3k holds. Plugging into (2.3) we obtain the upper bound (k_1) + 1. To get rid of the extra 1, we need to use the uniqueness part of the Hilton-Milner theorem [11] that we used to get our bound on h. It states that if k > 4 and an intersecting family F C (") with nFF = 0 has size (k_1) - ("k^1) + 1, then there exist x G [n] and x G G C [n] such that F = {G} U { F : x G F, F n G = 0}. Observe that for any H = G with x G H there exist lots of sets F G F that are disjoint with H, so only sets H' that contain x can be added to the Fj's. But as all Fj's consist of pairwise disjoint sets, such an H' can only be added to the Fj containing G. Also, at most one such set can be added as )gain this Fj consists of pairwise dis(oint sets. We obtained that if t > 2 and h = (k _ 1 ) - (" 1 ) + 1, then £= 1 |Fj| < (k _ 1 ) - (" k-7 1 ) + 2 < (k _ 1 ). Next, we assume that 2k + 2 < n < 3k. Then we have t < 2 and therefore the family F' := uh=1Fi has the property that for any F gF' there exists at most one other G gF' that is disjoint with F. Such families are called (< 1)-almost intersecting and Gerbner et al. [8] proved that whenever 2k + 2 < n holds, then any (< 1)-almost intersecting family G C (M) has size at most (nk _1). Finally,if n = 16, k = 4, (hen we need to bound h+m2 + m3 + m4 < h+m2 + 2m3 < h + 2m2 + 3m3. As (3kk) = (^ > 6(8) = (2kk), (2.2) implies 2m2 + 3m3 < (8). Using the Hilton-Milner bound h < (k _ 1) - (" 11) + 1 and plugging in n = 16, we obtain £h= 1 |Fi| < h + 2m2 + 3m3 < (k _ 1 ) - ( 3 ) + 1 + (4) < (k_ 1 ). This concludes the proof. □ 278 Ars Math. Contemp. 18 (2020) 187-210 Proof of Theorem 1.2. Theorem 1.4 shows that Knkjfc < (k-J) holds if n > 2k + 2. Observe that diam(Knkjfc) < 3 if and only if n > 2.5k - 0.5 (see e.g. [16]). Also, Theorem 1.3 yields that if the diameter of a graph G is at most 3, then any independent set in G is in general position. The largest independent sets in Knn k correspond to stars, i.e. families Sx = {H G ('k') : x G H} for some x G [n]. Therefore, gp(KnUjk) > (k-J) holds provided n > 2.5k — 0.5. If 2k + 2 < n < 2.5k — 0.5, then the upper bound of Theorem 1.4 is based on the result of Gerbner et al. [ ] on (< 1)-almost intersecting families. Their result also states that the only (< 1)-almost intersecting families of size (k-J ) are stars. But if n < 2.5k — 0.5, then {H G ('k') : 1 G H} is not in general position as shown by the following example: let n = 2k + M with 1 < M < 0.5k — 0.5 and FT = [k], F2 = {1, 2,..., k — M — 1} U {k + 1, k + 2,..., k + M + 1}. We claim that dKnn,k(Fj, F2) > 4. Indeed, as C := [n] \ (FT U F2) is of size k — 1, we have dKn (FT, F2) > 3. Suppose G i, G2 are k-subsets of [n] with FT n G i = G i n G2 = 0. Let us define t = |G i n F21. As G i is disjoint with Fi, so with FT n F2, we have t < M + 1. Therefore |C n G i| > k — M — 1 must hold. As G2 is disjoint with G j, we obtain |C n G2I < M, but as |Fj \ F2I = M +1 and 2M +1 < k, G2 must meet F2, so indeed dKn(FT, F2) > 4 holds. On the other hand, for any x G F2 \ Fj and y, z G Fj \ F2, the sets Fj, C U {x}, F2 \ {x} U {y}, C U {z}, F2 form a path of length 4, therefore a geodesic with 1 g F2 \ {x} U {z}. This shows that {H G ('k]) : 1 G H} is not in general position. Therefore if 2k + 2 < n < 2.5k — 0.5 holds, then we have gp(Knn,k) < (k-J ). Finally, let us consider the case n = 2k +1. Again, vertices corresponding to sets of stars are not in general position and all other independent sets have size smaller than (k-J ). So suppose F, F' are disjoint sets in a family F corresponding to vertices in general position. Then by Theorem 1.3, for any set G = F, F' in F we must have d(G, F) = d(G, F'). Observe that in Kn2k+ i,fc we have d(H, H') = min{2(k — |H nH'|), 2|H n H'| + 1}. Let us first assume that k = 21 + 1 is odd. Then by the above, for any G G F we must have |G n F| = |G n F' | = 1 and the unique element x G [2k + 1] \ (F U F') must belong to G. Therefore, with the notation of the proof of Theorem 1.4, we have m2 = 1 and h < tk- J) — tk--i1 ) + 1 and tas |F| < tk- J ) — tk--i1 ) + 2 < tk- J ). Let us assume that k = 21 is even. Then by the above, for any G = F, F' in F we must have |G n F | = |G n F '| = land thus G C F U F'. If we take one set from each disjoint pair, we obtain a family G C ('2k]) such that any pairwise intersection is of the same size. By Fisher's inequality, we obtain that the number m2 of paitrs i)s at most 2k. Moreover, as all sets of F are k-subsets of [2k], we must have h < J (2fcfc). Therefore, we need to show 2 fkO + 2k < (fc2- 1) = k+T which is equivalent to 2fc(fc2-+2) < t2fcfc). This holds for k > 4. □ 3 Concluding remarks First of all, it remains an open problem to determine gp(Knk,k) for 2k +1 < n < 2.5k — 0.5. Let us finish this short note with two remarks. First observe that an (< 1)-almost intersecting family F C ('k') corresponds to a subset U of the vertices of Knkjfc such that Knk k [U] does not contain a path on three vertices. There have been recent developments B. Patkos: On the general position problem on Kneser graphs 279 [1, 9, 15] in the general problem of finding the largest possible size of a subset U of the vertices of Knn,k such that Knn,k [U] does not contain some fixed forbidden graph F. Note that independently of the host graph G, if a subset S of the vertices of G is in general position, then G[S] cannot contain a path on three vertices as an induced subgraph. Returning to the Kneser graph Knn,k it would be interesting to address the induced version of the vertex Turan problems mentioned above. There have been lots of applications and generalizations of Bollobas's inequality. Very recently O'Neill and Verstraete [13] obtained Bollobas type results for k-tuples. Their condition to generalize disjoint pairs is completely different from the condition of Lemma 2.1. More importantly pairwise disjoint, cross-intersecting families were introduced by Renyi [14] as qualitatively independent partitions if the extra condition that U FF = [n] holds for all 1 < i < h is added, and the uniformity condition |F | = k for all F G Ulh=1Fi is replaced by |Fi| = d for all 1 < i < h. Gargano, Korner and Vaccaro proved [ ] that for any fixed d > 2 as n tends to infinity the maximum number of qualitatively independent d-partitions is 2(d-o(1))n. Based on their construction, for any fixed d one can obtain 2(2-o(1))k many pairwise disjoint cross-intersecting d-tuples of k-sets as k tends to infinity. ORCID iD Balazs Patkos©https://orcid.org/0000-0002-1651-2487 References [1] M. Alishahi and A. Taherkhani, Extremal G-free induced subgraphs of Kneser graphs, J. Comb. Theory Ser. A 159 (2018), 269-282, doi:10.1016/j.jcta.2018.06.010. [2] B. S. Anand, U. Chandran S. V., M. Changat, S. Klavzar and E. J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019), 84-89, doi:10.1016/j.amc.2019.04.064. [3] B. Bollobas, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447-452, doi: 10.1007/bf01904851. [4] S. V. Chandran and G. J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Comb. 4 (2016), 135-143, http://fs.unm.edu/IJMC/IJMC-4-2016.pdf. [5] P. Erd6s, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford 12 (1961), 313-320, doi:10.1093/qmath/12.1.313. [6] V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, Finding points in general position, Internal J. Comput. Geom. Appl. 27 (2017), 277-296, doi:10.1142/s021819591750008x. [7] L. Gargano, J. Korner and U. Vaccaro, Sperner capacities, Graphs Combin. 9 (1993), 31-46, doi:10.1007/bf01195325. [8] D. Gerbner, N. Lemons, C. Palmer, B. Patk6s and V. Szecsi, Almost intersecting families of sets, SIAMJ. Discrete Math. 26 (2012), 1657-1669, doi:10.1137/120878744. [9] D. Gerbner, A. Methuku, D. T. Nagy, B. Patk6s and M. Vizer, Stability results for vertex Turan problems in Kneser graphs, Electron. J. Combin. 26 (2019), #P2.13 (12 pages), doi:10.37236/ 8130. [10] M. Ghorbani, H. R. Maimani, M. Momeni, F. R. Mahid, S. Klavzar and G. Rus, The general position problem on kneser graphs and on some graph operations, Discuss. Math. Graph Theory (2020), doi:10.7151/dmgt.2269. 280 Ars Math. Contemp. 18 (2020) 187-210 [11] A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369-384, doi:10.1093/qmath/18.1.369. [12] P. Manuel and S. KlavZar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018), 177-187, doi:10.1017/s0004972718000473. [13] J. O'Neill and J. Verstraete, Bollobas-type inequalities on set k-tuples, 2018, arXiv:1812.00537v1 [math.CO]. [14] A. Renyi, Foundations of Probability, Wiley, 1971. [15] A. Taherkhani, Size and structure of large (s,t)-union intersecting families, 2019, arXiv:1903.02614 [math.CO]. [16] M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005), 383-385, doi:10.1016/j.disc.2005.10.001.