{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:25Z","timestamp":1740107125891,"version":"3.37.3"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T00:00:00Z","timestamp":1713916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"NKFIH","doi-asserted-by":"crossref","award":["SNN 129 364","FK 132060"],"award-info":[{"award-number":["SNN 129 364","FK 132060"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>A q<\/jats:italic>-graph H<\/jats:italic> on n<\/jats:italic> vertices is a set of vectors of length n<\/jats:italic> with all entries from $$\\{0,1,\\dots ,q\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n q<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and every vector (that we call a q<\/jats:italic>-edge) having exactly two non-zero entries. The support of a q<\/jats:italic>-edge $${\\textbf{x}}$$<\/jats:tex-math>\n x<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the pair $$S_{\\textbf{x}}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n x<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of indices of non-zero entries. We say that H<\/jats:italic> is an s<\/jats:italic>-copy of an ordinary graph F<\/jats:italic> if $$|H|=|E(F)|$$<\/jats:tex-math>\n \n |<\/mml:mo>\n H<\/mml:mi>\n |<\/mml:mo>\n =<\/mml:mo>\n |<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, F<\/jats:italic> is isomorphic to the graph with edge set $$\\{S_{\\textbf{x}}:{\\textbf{x}}\\in H\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n \n S<\/mml:mi>\n x<\/mml:mi>\n <\/mml:msub>\n :<\/mml:mo>\n x<\/mml:mi>\n \u2208<\/mml:mo>\n H<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and whenever $$v\\in e,e'\\in E(F)$$<\/jats:tex-math>\n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n e<\/mml:mi>\n ,<\/mml:mo>\n \n e<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n \n (<\/mml:mo>\n F<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the entries with index corresponding to v<\/jats:italic> in the q<\/jats:italic>-edges corresponding to e<\/jats:italic> and $$e'$$<\/jats:tex-math>\n \n e<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> sum up to at least s<\/jats:italic>. E.g., the q<\/jats:italic>-edges (1,\u00a03,\u00a00,\u00a00,\u00a00),\u00a0(0,\u00a01,\u00a00,\u00a00,\u00a03), and (3,\u00a00,\u00a00,\u00a00,\u00a01) form a 4-triangle. The Tur\u00e1n number $$\\mathop {}\\!\\textrm{ex}(n,F,q,s)$$<\/jats:tex-math>\n \n \n \n ex<\/mml:mtext>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n F<\/mml:mi>\n ,<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n s<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the maximum number of q<\/jats:italic>-edges that a q<\/jats:italic>-graph H<\/jats:italic> on n<\/jats:italic> vertices can have if it does not contain any s<\/jats:italic>-copies of F<\/jats:italic>. In the present paper, we determine the asymptotics of $$\\mathop {}\\!\\textrm{ex}(n,F,q,q+1)$$<\/jats:tex-math>\n \n \n \n ex<\/mml:mtext>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n F<\/mml:mi>\n ,<\/mml:mo>\n q<\/mml:mi>\n ,<\/mml:mo>\n q<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for many graphs F<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00373-024-02787-4","type":"journal-article","created":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T17:01:51Z","timestamp":1713978111000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extremal Graph Theoretic Questions for q-Ary Vectors"],"prefix":"10.1007","volume":"40","author":[{"given":"Bal\u00e1zs","family":"Patk\u00f3s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M\u00e1t\u00e9","family":"Vizer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,24]]},"reference":[{"key":"2787_CR1","unstructured":"G. Bacs\u00f3, Cs. Bujt\u00e1s, B. Patk\u00f3s, Zs. Tuza, M. Vizer. The robust chromatic number of a graph"},{"key":"2787_CR2","first-page":"51","volume":"1","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Simonovits, M.: A limit theorem in graph theory. Stud. Sci. Math. Hung. 1, 51\u201357 (1966)","journal-title":"Stud. Sci. Math. Hung."},{"key":"2787_CR3","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1090\/S0002-9904-1946-08715-7","volume":"52","author":"P Erd\u0151s","year":"1946","unstructured":"Erd\u0151s, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087\u20131091 (1946)","journal-title":"Bull. Am. Math. Soc."},{"key":"2787_CR4","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-39286-3_7","volume-title":"Erd\u00f6s Centennial","author":"Z F\u00fcredi","year":"2013","unstructured":"F\u00fcredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In: Erd\u00f6s Centennial, pp. 169\u2013264. Springer, Berlin (2013)"},{"key":"2787_CR5","volume-title":"Random Graphs","author":"S Janson","year":"2011","unstructured":"Janson, S., Ruci\u0144ski, A., \u0141uczak, T.: Random Graphs. Wiley, Hoboken (2011)"},{"key":"2787_CR6","series-title":"(Keszthely, 1993), Bolyai Soc. Math. Stud., 2","first-page":"295","volume-title":"Combinatorics, Paul Erd\u0151s is Eighty","author":"J Koml\u00f3s","year":"1996","unstructured":"Koml\u00f3s, J., Simonovits, M.: Szemer\u00e9di\u2019s regularity lemma and its applications in graph theory. In: Combinatorics, Paul Erd\u0151s is Eighty. (Keszthely, 1993), Bolyai Soc. Math. Stud., 2, vol. 2, pp. 295\u2013352. J\u00e1nos Bolyai Math. Soc, Budapest (1996)"},{"key":"2787_CR7","doi-asserted-by":"publisher","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"P K\u00f6v\u00e1ri","year":"1954","unstructured":"K\u00f6v\u00e1ri, P., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of Zarankiewicz. Colloquium Mathematicum 3, 50\u201357 (1954)","journal-title":"Colloquium Mathematicum"},{"issue":"10","key":"2787_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113506","volume":"346","author":"B Patk\u00f3s","year":"2023","unstructured":"Patk\u00f3s, B., Tuza, Zs., Vizer, M.: Vector sum-intersection theorems. Discret. Math. 346(10), 113506 (2023)","journal-title":"Discret. Math."},{"key":"2787_CR9","first-page":"399","volume-title":"Colloques Internationaux C.N.R.S. 260, Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes","author":"E Szemer\u00e9di","year":"1976","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Colloques Internationaux C.N.R.S. 260, Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, pp. 399\u2013401. Univ. Orsay, Orsay (1976)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02787-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02787-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02787-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T04:04:16Z","timestamp":1721707456000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02787-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,24]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["2787"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02787-4","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,4,24]]},"assertion":[{"value":"3 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"57"}}