{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:05Z","timestamp":1787323145661,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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\u00f6s--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.<\/jats:p>","DOI":"10.1137\/20m1321760","type":"journal-article","created":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T11:21:25Z","timestamp":1622546485000},"page":"1136-1148","source":"Crossref","is-referenced-by-count":7,"title":["Bipartite Independence Number in Graphs with Bounded Maximum Degree"],"prefix":"10.1137","volume":"35","author":[{"given":"Maria","family":"Axenovich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-S\u00e9bastien","family":"Sereni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Snyder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lea","family":"Weber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,6,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1906"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22639"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.11.002"},{"key":"atypb4","first-page":"35","volume":"10","author":"Balbuena C.","year":"2008","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb5","first-page":"17","author":"Beineke L. W.","year":"1975","journal-title":"Aberdeen"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.2307\/2043545"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-036-2"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.37236\/1561"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21730"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.4064\/ap-3-1-165-168"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"atypb12","first-page":"64","volume":"10","author":"Erd\u00f6s P.","year":"2000","journal-title":"Geombinatorics"},{"key":"atypb13","first-page":"215","volume":"1","author":"Erd\u00f6s P.","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"atypb14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/jgt.20456","volume":"64","author":"Feige U.","year":"2010","journal-title":"J. Graph Theory"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001814"},{"key":"atypb16","first-page":"169","author":"F\u00fcredi Z.","year":"2013","journal-title":"Berlin"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1996.0133"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199811)29:3<185::AID-JGT6>3.0.CO;2-M"},{"key":"atypb19","first-page":"217","volume":"53","author":"Hattingh J. H.","year":"1998","journal-title":"Util. Math."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1017\/S0017089500003323"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucinski,\n                      Random Graphs\n                      , Wiley Ser. Discrete Math. Optim., Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/19M125786X"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.37236\/1819"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020254"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759743"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80038-3"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1321760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:29Z","timestamp":1787319869000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1321760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1321760"],"URL":"https:\/\/doi.org\/10.1137\/20m1321760","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}