Maximum bipartite subgraphs in H -free graphs

Jing Lin

Czechoslovak Mathematical Journal (2022)

  • Volume: 72, Issue: 3, page 621-635
  • ISSN: 0011-4642

Abstract

top
Given a graph G , let f ( G ) denote the maximum number of edges in a bipartite subgraph of G . Given a fixed graph H and a positive integer m , let f ( m , H ) denote the minimum possible cardinality of f ( G ) , as G ranges over all graphs on m edges that contain no copy of H . In this paper we prove that f ( m , θ k , s ) ≥ 1 2 m + Ω ( m ( 2 k + 1 ) / ( 2 k + 2 ) ) , which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write K k ' and K t , s ' for the subdivisions of K k and K t , s . We show that f ( m , K k ' ) ≥ 1 2 m + Ω ( m ( 5 k - 8 ) / ( 6 k - 10 ) ) and f ( m , K t , s ' ) ≥ 1 2 m + Ω ( m ( 5 t - 1 ) / ( 6 t - 2 ) ) , improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003).

How to cite

top

Lin, Jing. "Maximum bipartite subgraphs in $H$-free graphs." Czechoslovak Mathematical Journal 72.3 (2022): 621-635. <http://eudml.org/doc/298359>.

@article{Lin2022,
abstract = {Given a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,\theta _\{k,s\})\ge \tfrac\{1\}\{2\} m +\Omega (m^\{(2k+1)/(2k+2)\})$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K^\{\prime \}_\{k\}$ and $K^\{\prime \}_\{t,s\}$ for the subdivisions of $K_k$ and $K_\{t,s\}$. We show that $f(m,K^\{\prime \}_\{k\})\ge \tfrac\{1\}\{2\} m +\Omega (m^\{(5k-8)/(6k-10)\})$ and $f(m,K^\{\prime \}_\{t,s\})\ge \tfrac\{1\}\{2\} m +\Omega (m^\{(5t-1)/(6t-2)\})$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003).},
author = {Lin, Jing},
journal = {Czechoslovak Mathematical Journal},
keywords = {bipartite subgraph; $H$-free; partition},
language = {eng},
number = {3},
pages = {621-635},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Maximum bipartite subgraphs in $H$-free graphs},
url = {http://eudml.org/doc/298359},
volume = {72},
year = {2022},
}

TY - JOUR
AU - Lin, Jing
TI - Maximum bipartite subgraphs in $H$-free graphs
JO - Czechoslovak Mathematical Journal
PY - 2022
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 72
IS - 3
SP - 621
EP - 635
AB - Given a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,\theta _{k,s})\ge \tfrac{1}{2} m +\Omega (m^{(2k+1)/(2k+2)})$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K^{\prime }_{k}$ and $K^{\prime }_{t,s}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K^{\prime }_{k})\ge \tfrac{1}{2} m +\Omega (m^{(5k-8)/(6k-10)})$ and $f(m,K^{\prime }_{t,s})\ge \tfrac{1}{2} m +\Omega (m^{(5t-1)/(6t-2)})$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003).
LA - eng
KW - bipartite subgraph; $H$-free; partition
UR - http://eudml.org/doc/298359
ER -

References

top
  1. Alon, N., 10.1007/BF01261315, Combinatorica 16 (1996), 301-311. (1996) Zbl0860.05043MR1417340DOI10.1007/BF01261315
  2. Alon, N., Bollobás, B., Krivelevich, M., Sudakov, B., 10.1016/S0095-8956(03)00036-4, J. Comb. Theory, Ser. B 88 (2003), 329-346. (2003) Zbl1030.05060MR1983363DOI10.1016/S0095-8956(03)00036-4
  3. Alon, N., Halperin, E., 10.1016/S0012-365X(97)00041-1, Discrete Math. 181 (1998), 19-29. (1998) Zbl0903.05028MR1600727DOI10.1016/S0012-365X(97)00041-1
  4. Alon, N., Krivelevich, M., Sudakov, B., 10.1017/S0963548305007017, Comb. Probab. Comput. 14 (2005), 629-647. (2005) Zbl1081.05047MR2174649DOI10.1017/S0963548305007017
  5. Bollobás, B., Scott, A. D., Better bounds for Max Cut, Contemporary Combinatorics Bolyai Society Mathematical Studies 10. Springer, Berlin (2002), 185-246. (2002) Zbl1014.90082MR1919571
  6. Bollobás, B., Scott, A. D., 10.1002/rsa.10062, Random Struct. Algorithms 21 (2002), 414-430. (2002) Zbl1013.05059MR1945378DOI10.1002/rsa.10062
  7. Conlon, D., Lee, J., Janzer, O., 10.1007/s00493-020-4202-1, Combinatorica 41 (2021), 465-494. (2021) Zbl07413845MR4328719DOI10.1007/s00493-020-4202-1
  8. Edwards, C. S., 10.4153/CJM-1973-048-x, Can. J. Math. 25 (1973), 475-485. (1973) Zbl0254.05116MR0337686DOI10.4153/CJM-1973-048-x
  9. Edwards, C. S., An improved lower bound for the number of edges in a largest bipartite subgraph, Recent Advances in Graph Theory Academia, Prague (1975), 167-181. (1975) Zbl0326.05115MR0398888
  10. Erdős, P., Gallai, T., 10.1007/BF02024498, Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. (1959) Zbl0090.39401MR0114772DOI10.1007/BF02024498
  11. Erdős, P., Gyárfás, A., Kohayakawa, Y., 10.1016/S0012-365X(97)00004-6, Discrete Math. 177 (1997), 267-271. (1997) Zbl0888.05035MR1483451DOI10.1016/S0012-365X(97)00004-6
  12. Faudree, R. J., Simonovits, M., 10.1007/BF02579343, Combinatorica 3 (1983), 83-93. (1983) Zbl0521.05037MR0716423DOI10.1007/BF02579343
  13. Janzer, O., 10.37236/8262, Electron. J. Comb. 26 (2019), Article ID P3.3, 6 pages. (2019) Zbl1416.05152MR3982312DOI10.37236/8262
  14. Jensen, T. R., Toft, B., 10.1002/9781118032497, John Wiley & Sons, New York (1995). (1995) Zbl0855.05054MR1304254DOI10.1002/9781118032497
  15. Li, Y., Rousseau, C. C., Zang, W., 10.1007/s003730170060, Graphs Comb. 17 (2001), 123-128. (2001) Zbl0979.05078MR1828633DOI10.1007/s003730170060
  16. Poljak, S., Tuza, Z., 10.1137/S0895480191196824, SIAM J. Discrete Math. 7 (1994), 307-313. (1994) Zbl0806.68086MR1272003DOI10.1137/S0895480191196824
  17. Scott, A., 10.1017/CBO9780511734885.006, Surveys in Combinatorics 2005 London Mathematical Society Lecture Note Series 327. Cambridge University Press, Cambridge (2005), 95-117. (2005) Zbl1110.05084MR2187736DOI10.1017/CBO9780511734885.006
  18. Shearer, J. B., 10.1002/rsa.3240030211, Random Struct. Algorithms 3 (1992), 223-226. (1992) Zbl0765.05057MR1151364DOI10.1002/rsa.3240030211
  19. Shearer, J. B., 10.1002/rsa.3240070305, Random Struct. Algorithms 7 (1995), 269-271. (1995) Zbl0834.05030MR1369066DOI10.1002/rsa.3240070305
  20. Wei, V., A lower bound on the stability number of a simple graph, Technical Report 81-11217-9 Bell Laboratories Technical Memorandum, New Jersey (1981). (1981) 
  21. Zeng, Q., Hou, J., 10.1017/S0004972716001295, Bull. Aust. Math. Soc. 96 (2017), 1-13. (2017) Zbl1367.05110MR3668394DOI10.1017/S0004972716001295
  22. Zeng, Q., Hou, J., 10.26493/1855-3974.1218.5ed, Ars Math. Contemp. 15 (2018), 147-160. (2018) Zbl1404.05092MR3862083DOI10.26493/1855-3974.1218.5ed

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.