[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

Search:


View post   

>> No.12665694 [View]
File: 18 KB, 259x259, 1 (214).jpg [View same] [iqdb] [saucenao] [google]
12665694

>>12663969
An idea: define a bipartite graph: the vertices are 1, 2, ...n and 1', 2', ... n', and you put an edge (i, j') in your graph iff the square (i, j) is filled.
Then, a rectangle in the picture <=> a 4-length cycle in this graph.
This turns out to be googleable
https://math.stackexchange.com/questions/1713140/maximize-the-number-of-edges-in-a-bipartite-graph-with-no-4-cycles
the correct asymptotics is apparently O(n^3/2)

Navigation
View posts[+24][+48][+96]