×

Bipartite independence number in graphs with bounded maximum degree. (English) Zbl 1465.05123

Summary: We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size \(t\) in a bipartite graph \(G\) with a fixed bipartition is an independent set with exactly \(t\) vertices in each part; in other words, it is a copy of \(K_{t, t}\) in the bipartite complement of \(G\). Let \(f(n,\Delta)\) be the largest \(k\) for which every \(n\times n\) bipartite graph with maximum degree \(\Delta\) in one of the parts has a bi-hole of size \(k\). Determining \(f(n,\Delta)\) is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. It has connections to the bipartite version of the Erdős-Hajnal conjecture, bipartite Ramsey numbers, and the Zarankiewicz problem. Our main result determines the asymptotic behavior of \(f(n,\Delta)\). More precisely, we show that for large but fixed \(\Delta\) and \(n\) sufficiently large, \(f(n,\Delta)=\Theta(\frac{\log\Delta}{\Delta}n)\). We further address more specific regimes of \(\Delta\), especially when \(\Delta\) is a small fixed constant. In particular, we determine \(f(n, 2)\) exactly and obtain bounds for \(f(n, 3)\), though determining the precise value of \(f(n, 3)\) is still open.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C07 Vertex degrees
05C35 Extremal problems in graph theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Alon, L. Rónyai, and T. Szabó, Tibor, Norm-graphs: Variations and applications, J. Combin. Theory Ser. B, 76 (1999), pp. 280-290. · Zbl 0935.05054
[2] M. Axenovich, C. Tompkins, and L. Weber, Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs, J. Graph Theory, 97 (2021), pp. 34-46. · Zbl 1521.05119
[3] C. Balbuena, P. García-Vázquez, X. Marcote, and J. C. Valenzuela, New results on the Zarankiewicz problem, Discrete Math., 307 (2007), pp. 2322-2327. · Zbl 1123.05050
[4] C. Balbuena, P. García-Vázquez, X. Marcote, and J. C. Valenzuela, Extremal \(K_{(s,t)}\)-free bipartite graphs, Discrete Math. Theor. Comput. Sci., 10 (2008), pp. 35-48. · Zbl 1196.05041
[5] L. W. Beineke and A. J. Schwenk, On a bipartite form of the Ramsey problem, in Proceedings of the Fifth British Combinatorial Conference, University of Aberdeen, Aberdeen, 1975, pp. 17-22. · Zbl 0333.05118
[6] B. Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc., 83 (1981), pp. 433-436. · Zbl 0474.05057
[7] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9 (1966), pp. 281-285. · Zbl 0178.27302
[8] Y. Caro and C. Rousseau, Asymptotic bounds for bipartite Ramsey numbers, Electron. J. Combin., 8 (2001), R17. · Zbl 0964.05044
[9] M. Chudnovsky, The Erdös-Hajnal conjecture-a survey, J. Graph Theory, 75 (2014), pp. 178-190. · Zbl 1280.05086
[10] K. Čulík, Teilweise Lösung eines verallgemeinerten Problems von K. Zarankiewicz, Ann. Polon. Math., 3 (1956), pp. 165-168. · Zbl 0071.01205
[11] P. Erdös and A. Hajnal, Ramsey-type theorems, Discrete Appl. Math., 25 (1989), pp. 37-52. · Zbl 0715.05052
[12] P. Erdös, A. Hajnal, and J. Pach, A Ramsey-type theorem for bipartite graphs, Geombinatorics, 10 (2000), pp. 64-68. · Zbl 0978.05052
[13] P. Erdös, A. Rényi, and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar., 1 (1966), pp. 215-235. · Zbl 0144.23302
[14] U. Feige and S. Kogan, Balanced coloring of bipartite graphs, J. Graph Theory, 64 (2010), pp. 277-291. · Zbl 1205.05087
[15] Z. Füredi, An upper bound on Zarankiewicz’ problem, Combin. Probab. Comput., 5 (1996), pp. 29-33. · Zbl 0857.05048
[16] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdös Centennial, Bolyai Soc. Math. Stud. 25, Springer-Verlag, Berlin, 2013, pp. 169-264. · Zbl 1296.05098
[17] J. R. Griggs and J. Ouyang, \((0,1)\)-matrices with no half-half submatrix of ones, European J. Combin., 18 (1997), pp. 751-761. · Zbl 0887.05037
[18] J. R. Griggs, M. Simonovits, and G. R. Thomas, Extremal graphs with bounded densities of small subgraphs, J. Graph Theory, 29 (1998), pp. 185-207. · Zbl 0919.05031
[19] J. H. Hattingh and M. A. Henning, Bipartite Ramsey theory, Util. Math., 53 (1998), pp. 217-230. · Zbl 0908.05064
[20] R. W. Irving, A bipartite Ramsey problem and the Zarankiewicz numbers, Glasg. Math. J., 19 (1978), pp. 13-26. · Zbl 0367.05051
[21] S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, Wiley Ser. Discrete Math. Optim., Wiley, New York, 2000. · Zbl 0968.05003
[22] D. Korándi, J. Pach, and I. Tomon, Large homogeneous submatrices, SIAM J. Discrete Math., 34 (2020), pp. 2532-2552. · Zbl 1460.05031
[23] T. Kövári, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math., 3 (1954), pp. 50-57. · Zbl 0055.00704
[24] B. D. McKay, N. C. Wormald, and B. Wysocka, Short cycles in random regular graphs, Electron. J. Combin., 11, (2004), R66. · Zbl 1063.05122
[25] I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar., 9 (1958), pp. 269-273. · Zbl 0084.01303
[26] M. Rosenfeld, Independent sets in regular graphs, Israel J. Math., 2 (1964), pp. 262-272. · Zbl 0134.43501
[27] A. Thomason, On finite Ramsey numbers, European J. Combin., 3 (1982), pp. 263-273. · Zbl 0503.05046
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.