×

Extremal graph theoretic questions for \(q\)-ary vectors. (English) Zbl 1539.05060

Summary: A \(q\)-graph \(H\) on \(n\) vertices is a set of vectors of length \(n\) with all entries from \(\{0,1,\ldots,q\}\) and every vector (that we call a \(q\)-edge) having exactly two non-zero entries. The support of a \(q\)-edge \(\mathfrak{x}\) is the pair \(S_{\mathfrak{x}}\) of indices of non-zero entries. We say that \(H\) is an \(s\)-copy of an ordinary graph \(F\) if \(|H|=|E(F)|, F\) is isomorphic to the graph with edge set \(\{S_{\mathfrak{x}}:\mathfrak{x}\in H\}\), and whenever \(v\in e\), \(e^\prime \in E(F)\), the entries with index corresponding to \(v\) in the \(q\)-edges corresponding to \(e\) and \(e^\prime \) sum up to at least \(s\). E.g., the \(q\)-edges (1, 3, 0, 0, 0), (0, 1, 0, 0, 3), and (3, 0, 0, 0, 1) form a 4-triangle. The Turán number \(\mathrm{ex}(n,F,q,s)\) is the maximum number of \(q\)-edges that a \(q\)-graph \(H\) on \(n\) vertices can have if it does not contain any \(s\)-copies of \(F\). In the present paper, we determine the asymptotics of \(\mathrm{ex}(n,F,q,q+1)\) for many graphs \(F\).

MSC:

05C30 Enumeration in graph theory
05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs

References:

[1] G. Bacsó, Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer. The robust chromatic number of a graph
[2] Erdős, P.; Simonovits, M., A limit theorem in graph theory, Stud. Sci. Math. Hung., 1, 51-57, 1966 · Zbl 0178.27301
[3] Erdős, P.; Stone, AH, On the structure of linear graphs, Bull. Am. Math. Soc., 52, 1087-1091, 1946 · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[4] Füredi, Z.; Simonovits, M., The history of degenerate (bipartite) extremal graph problems, Erdös Centennial, 169-264, 2013, Berlin: Springer, Berlin · Zbl 1296.05098 · doi:10.1007/978-3-642-39286-3_7
[5] Janson, S.; Ruciński, A.; Łuczak, T., Random Graphs, 2011, Hoboken: Wiley, Hoboken
[6] Komlós, J.; Simonovits, M., Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is Eighty, 295-352, 1996, Budapest: János Bolyai Math. Soc, Budapest · Zbl 0851.05065
[7] Kövári, P.; Sós, VT; Turán, P., On a problem of Zarankiewicz, Colloquium Mathematicum, 3, 50-57, 1954 · Zbl 0055.00704 · doi:10.4064/cm-3-1-50-57
[8] Patkós, B.; Tuza, Zs; Vizer, M., Vector sum-intersection theorems, Discret. Math., 346, 10, 2023 · Zbl 1518.05190 · doi:10.1016/j.disc.2023.113506
[9] Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. 260, Problèmes Combinatoires et Théorie des Graphes, 399-401, 1976, Orsay: Univ. Orsay, Orsay · Zbl 0413.05055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.