On a Relation between Schreier-type Sets and a Modification of Tur\'{a}n Graphs

zbMATH Open1514.05080arXiv2205.08280MaRDI QIDQ6399368FDOQ6399368

Authors: Hùng Viẹt Chu 

Publication date: 16 May 2022

Abstract: Recently, a relation between Schreier-type sets and Tur'{a}n graphs was discovered. In this note, we give a combinatorial proof and obtain a generalization of the relation. Specifically, for $p,qge1$, let ${\displaystyle }$mathcal{A}_q := {Fsubsetmathbb{N}: |F| = 1 mbox{ or }Fmbox{ is an arithmetic progression with difference } q}${\displaystyle }$ and ${\displaystyle }$Sr(n, p, q) := #{Fsubset {1, ldots, n},:, pmin Fge |F|mbox{ and }Fin mathcal{A}_q}.${\displaystyle }$ We show that ${\displaystyle }$Sr(n, p, q) = T(n+1, pq+1, q),${\displaystyle }$ where $T(cdot,cdot,cdot)$ is the number of edges of an $n$-vertex graph that is a modification of Tur'{a}n graphs. We also prove that $Sr(n,p,q)$ is the partial sum of certain sequences.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

This page was built for publication: On a Relation between Schreier-type Sets and a Modification of Tur\'{a}n Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399368)