The bipartite Turán number of a graph H, denoted by ex(m,n;H), is the maximum number of edges in any bipartite graph G=(A,B;E(G))with | A |=mand | B |=nwhich does not contain H as a subgraph. Whenmin{ m,n }>2t...The bipartite Turán number of a graph H, denoted by ex(m,n;H), is the maximum number of edges in any bipartite graph G=(A,B;E(G))with | A |=mand | B |=nwhich does not contain H as a subgraph. Whenmin{ m,n }>2t, the problem of determining the value of ex(m,n;Km−t,n−t)has been solved by Balbuena et al. in 2007, whose proof focuses on the structural analysis of bipartite graphs. In this paper, we provide a new proof on the value of ex(m,n;Km−t,n−t)by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using { 0,1 }-matrices due to Zarankiewicz [Problem P 101. Colloquium Mathematicum, 2(1951), 301].展开更多
We investigate the impact of a high-degree vertex in Turán problems for degenerate hypergraphs(including graphs).We say an r-graph F is bounded if there exist constantsα,β>0 such that for large n,every n-ver...We investigate the impact of a high-degree vertex in Turán problems for degenerate hypergraphs(including graphs).We say an r-graph F is bounded if there exist constantsα,β>0 such that for large n,every n-vertex F-free r-graph with a vertex of degree at least\(\alpha\left({\matrix{{n-1}\cr{r-1}}}\right)\)has fewer than(1−β)·ex(n,F)edges.The boundedness property is crucial for recent works that aim to extend the classical Hajnal–Szemerédi Theorem(Toward a density Corrádi–Hajnal theorem for degenerate hypergraphs.J.Combin.Theory Ser.B,172,221–262(2025))and the anti-Ramsey theorems of Erdős–Simonovits–Sós(Tight bounds for rainbow partial F-tiling in edge-colored complete hypergraphs.J.Graph Theory,110(4),457–467(2025)).We show that many well-studied degenerate hypergraphs,such as all even cycles,most complete bipartite graphs,and the expansion of most complete bipartite graphs,are bounded.In addition,to prove the boundedness of the expansion of complete bipartite graphs,we introduce and solve a Zarankiewicz-type problem for 3-graphs,strengthening a theorem by Kostochka–Mubayi–Verstraëte(Turán problems and shadows III:expansions of graphs.SIAM J.Discrete Math.,29(2),868–876(2015)).展开更多
文摘The bipartite Turán number of a graph H, denoted by ex(m,n;H), is the maximum number of edges in any bipartite graph G=(A,B;E(G))with | A |=mand | B |=nwhich does not contain H as a subgraph. Whenmin{ m,n }>2t, the problem of determining the value of ex(m,n;Km−t,n−t)has been solved by Balbuena et al. in 2007, whose proof focuses on the structural analysis of bipartite graphs. In this paper, we provide a new proof on the value of ex(m,n;Km−t,n−t)by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using { 0,1 }-matrices due to Zarankiewicz [Problem P 101. Colloquium Mathematicum, 2(1951), 301].
基金Supported by the National Key R&D Program of China(Grant No.2023YFA1010202)supported by the Central Guidance on Local Science and Technology Development Fund of Fujian Province(Grant No.2023L3003)+1 种基金supported by the National Natural Science Foundation of China(Grant Nos.12501487,12571367)supported by the Excellent Young Talents Program(Overseas)of the National Natural Science Foundation of China and by the ERC Advanced Grant(Grant No.101020255)。
文摘We investigate the impact of a high-degree vertex in Turán problems for degenerate hypergraphs(including graphs).We say an r-graph F is bounded if there exist constantsα,β>0 such that for large n,every n-vertex F-free r-graph with a vertex of degree at least\(\alpha\left({\matrix{{n-1}\cr{r-1}}}\right)\)has fewer than(1−β)·ex(n,F)edges.The boundedness property is crucial for recent works that aim to extend the classical Hajnal–Szemerédi Theorem(Toward a density Corrádi–Hajnal theorem for degenerate hypergraphs.J.Combin.Theory Ser.B,172,221–262(2025))and the anti-Ramsey theorems of Erdős–Simonovits–Sós(Tight bounds for rainbow partial F-tiling in edge-colored complete hypergraphs.J.Graph Theory,110(4),457–467(2025)).We show that many well-studied degenerate hypergraphs,such as all even cycles,most complete bipartite graphs,and the expansion of most complete bipartite graphs,are bounded.In addition,to prove the boundedness of the expansion of complete bipartite graphs,we introduce and solve a Zarankiewicz-type problem for 3-graphs,strengthening a theorem by Kostochka–Mubayi–Verstraëte(Turán problems and shadows III:expansions of graphs.SIAM J.Discrete Math.,29(2),868–876(2015)).
