On subgraphs of tripartite graphs

DOI10.1016/J.DISC.2022.113152MaRDI QIDQ2092375zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.08055

zbMATH Keywords

tripartite graphsTurán-type problemsZarankiewicz problem

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: Bollob'{a}s, ErdH{o}s, and Szemer'{e}di [Discrete Math 13 (1975), 97--107] investigated a tripartite generalization of the Zarankiewicz problem: what minimum degree forces a tripartite graph with $n$ vertices in each part to contain an octahedral graph $K_3(2)$? They proved that $n+2^{-1/2}{n}^{3/4}$ suffices and suggested it could be weakened to $n+c{n}^{1/2}$ for some constant $c>0$. In this note we show that their method only gives $n+(1+o(1))n^{11/12}$ and provide many constructions that show if true, $n+c{n}^{1/2}$ is better possible.

Recommendations

• Observer with a constant proper acceleration
• scientific article; zbMATH DE number 4003000
• An effective theory of metrics with maximal proper acceleration
• Eternally accelerating universe without event horizon
• scientific article; zbMATH DE number 1834064

Cites work

• Complete subgraphs in a multipartite graph
• Extremal problems for transversals in graphs with bounded degree
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Odd Independent Transversals are Odd
• On a problem of K. Zarankiewicz
• On complete subgraphs of r-chromatic graphs
• On extremal problems of graphs and generalized graphs
• On Graphs that do not Contain a Thomsen Graph
• Über ein Problem von K. Zarankiewicz

Cited in

(5)

• Planar polynomials and an extremal problem of Fischer and Matoušek
• Tripartite multidigraphs and imbalances
• The minimal density of triangles in tripartite graphs
• Can an observer really catch up with light?
• The Zarankiewicz problem in 3-partite graphs

This page was built for publication: On subgraphs of tripartite graphs

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