Extremal numbers of hypergraph suspensions of even cycles

被引:0
作者
Mukherjee, Sayan [1 ,2 ]
机构
[1] Blueqat Res, Tokyo 1506139, Japan
[2] Univ Tokyo, Dept Phys, Tokyo 1130033, Japan
关键词
GRAPHS; CONSTRUCTIONS;
D O I
10.1016/j.ejc.2024.103935
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For fixed k >= 2, determining the order of magnitude of the number of edges in an n-vertex bipartite graph not containing C-2k, the cycle of length 2k, is a long-standing open problem. We consider an extension of this problem to triple systems. In particular, we prove that the maximum number of triples in an n-vertex triple system which does not contain a C-6 in the link of any vertex, has order of magnitude n(7/3). Additionally, we construct new families of dense C-6-free bipartite graphs with n vertices and n(4/3) edges in order of magnitude. (c) 2024 Elsevier Ltd. All rights reserved.
引用
收藏
页数:16
相关论文
共 29 条
[11]   On the connectivity of certain graphs of high girth [J].
Lazebnik, F ;
Viglione, R .
DISCRETE MATHEMATICS, 2004, 277 (1-3) :309-319
[12]   A NEW SERIES OF DENSE GRAPHS OF HIGH GIRTH [J].
LAZEBNIK, F ;
USTIMENKO, VA ;
WOLDAR, AJ .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 32 (01) :73-79
[13]  
Lazebnik F, 1999, DISCRETE MATH, V197, P503
[14]   EXPLICIT CONSTRUCTION OF GRAPHS WITH AN ARBITRARY LARGE GIRTH AND OF LARGE-SIZE [J].
LAZEBNIK, F ;
USTIMENKO, VA .
DISCRETE APPLIED MATHEMATICS, 1995, 60 (1-3) :275-284
[15]   A note on inversion of Toeplitz matrices [J].
Lv, Xiao-Guang ;
Huang, Ting-Zhu .
APPLIED MATHEMATICS LETTERS, 2007, 20 (12) :1189-1193
[16]   EXPLICIT CONSTRUCTIONS OF GRAPHS WITHOUT SHORT CYCLES AND LOW-DENSITY CODES [J].
MARGULIS, GA .
COMBINATORICA, 1982, 2 (01) :71-78
[17]   Constructions of bipartite graphs from finite geometries [J].
Mellinger, KE ;
Mubayi, D .
JOURNAL OF GRAPH THEORY, 2005, 49 (01) :1-10
[18]   LDPC codes from triangle-free line sets [J].
Mellinger, KE .
DESIGNS CODES AND CRYPTOGRAPHY, 2004, 32 (1-3) :341-350
[19]   Some exact results and new asymptotics for hypergraph Turan numbers [J].
Mubayi, D .
COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (03) :299-309
[20]  
Mubayi Dhruv., 2020, TRIANGLES GRAPHS BIP