一個不含 K_2,2 的二分極圖是一個含有最多邊數且不含有子圖 K_2,2 的二分圖。若此二分圖為 K_m,n 的子圖，則求此二分極圖的邊數的問題也就是出名的Zarankiewicz 問題。在本論文中，我們令f(m,n)為 K_m,n 中不含 K_2,2 的二分極圖的邊數。我們獲得以下的結果：
①f(m,n)≤n/2+√(mn(m-1)+n^2/4)   
②若 n≥(m|2)，則 f(m,n)=(m|2)+n。
③若 m≡1,3 (mod 6)，則 K_m 恰可分割成 m(m-1)/6 個邊相異的 K_3 子圖，且f(m,n)=(m|2)。
④若 ((m|2))/3≤n≤(m|2)，則 f(m,n)=[((m|2)+3n)/2]  。
⑤若 m≡1,4 (mod 12)，則 K_m 恰可分割成 m(m-1)/12 個邊相異的 K_4  子圖，且，f(m,n)=2(m|2)/3。

An extremal K_2,2-free bipartite graphs is a bipartite graph which contains the maximum number of edges and does not contain any subgraph K_2,2. If this bipartite graph is a subgraph of K_m,n, then finding the number of edges of the extremal bipartite graph is the well-known Zarankiewicz Problem. In this thesis, we let f(m,n) be the number of edges of the extremal K_2,2-free bipartite graph which is a subgraph of K_m,n. We obtain the following results:
①f(m,n)≤n/2+√(mn(m-1)+n^2/4)
②If ≥(m|2), then f(m,n)=(m|2)+n.
③If m≡1,3 (mod 6), then K_m  decompose into (m(m-1))/6 edge-disjoint K_3 subgraphs, and f(m,n)=(m|2).
④If ((m|2))/3≤n≤(m|2), then f(m,n)=[((m|2)+3n)/2]  .
⑤If m≡1,4 (mod 12), then K_m decompose into (m(m-1))/12 edge-disjoint K_4 subgraphs, and f(m,n)=2(m|2)/3.

目錄

第一章  簡介	1
第二章  預備知識	3
第三章  主要內容	11
第3.1節	Zarankiewicz 問題	11
第3.2節	求f(m,n)值		11
第3.3節	二分圖與 f(m,n)  		14
第3.4節	K_m 的裝填與 f(m,n)  	17
參考文獻				32
 
	圖表目錄	
圖1	圖G	                        4
圖2	完全圖 K_m	                6
圖3	完全二分圖 K_m,n	                7
表1	鄰接矩陣	                        5
表2	關聯矩陣	                        6
表3	匹配	                        9
表4	K_8 的完美匹配                    9
表5	K_5 的分割與裝填                  10
表6	2×2 矩陣                        11
表7	在2×n 矩陣加入1~2行               12
表8	二種添加方式                      12
表9	加入的每行只能有1個1               13
表10	f(4,4) 與f(4,5)                 14
表11	矩陣與二分圖轉換1                  15
表12	矩陣與二分圖轉換2                  15
表13	矩陣與二分圖轉換3                  15-16
表14	出現 J_2×2 的情形                 16
表15	導出子圖	                        17-18
表16	m=4 的導出子圖	                19
表17	m=5、6、7 時的 f(m,n) 值	        19
表18	K_7 分割成7個 K_3 子圖	        23
表19	多加1個子圖時	                23
表20	多加2個子圖時	                23
表21	以 K_3 裝填 K_m 時的最小殘留	25
表22	((m|2))/3≤n≤(m|2)時f(m,n)之值	27-28
表23	m≤n≤((m|2))/3時f(m,n) 之值	30-31

[1] Bollobes, B., “Extremal Graph Theory,” Academic Press, New York, 1978.
[2] Colbourn, Charles J. and Dinitz, Jeffrey H., The CRC Handbook of Combinatorial Designs, CRC Press, 1996.
[3] Culik, K., Teilwesise Losung eines verallgemeinerten Problems von Zarankiewicz, Anna. Soc. Polon. Math. 3 (1956), 165-168. 
[4] Goddard, W., M.A. Henning and O.R. Oellermann, Bipartite Ramsey numbers and Zarankiewicz numbers, Discrete Math. 219 (2000), 85-89.
[5] Griggs, J., and H. Chih-Chang, On the half-half case of the Zarankiewicz problem, Discrete Math. 249 (2002), 9-104. 
[6] Griggs, J., and J. Ouyang, (0,1)-Matrices with no half-half submatrix of ones, European J. Combinatorics 18 (1997), 751-761.
[7] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Rosentstiehl, P. ed.) Gordon and Breach, New York (1967), 139-142.
[8] Guy, R.K., A problem of Zarankiewicz Theory of Graphs, (Erdos, P. and Kantona G., eds.) Academic Press, New York (1968), 119-150
[9] Guy, R.K., The many faceted problem of Zarankiewicz The Many Facets of Graphs Theory, Lecture Notes in Maths 110, pringer,(1969), 129-148.
[10] Guy, R.K., and S. Znam, A problem of Zarankiewicz Recent progress in Combinatorics, (Tutte, W.T., ed.) Academic Press, New York (1969), 237-243.
[11] Kirkman,Thomas P., On a Problem in Combinations, The Cambridge and Dublin Mathematical Journal. (Macmillan, Barclay, and Macmillan) 2 (1847), 191–204.
[12] Sierpinski, S., Sur un probleme concernant un reseau a 36 points, Ann. Pol. Math. 24 (1951), 173-174.
[13] Zarankiewicz, K. Problem P 101, Colloq. Math. 2 (1951), 301.
[14] 傅恆霖(Hung-Lin Fu),組合設計講義Combinational Designs (Lecture Notes), 65-78 http://www.math.nctu.edu.tw/hlfu/getCourseFile.php?CID=48&type=browser