agm_bound (817B)
1 # AGM bound 2 3 Statement: for Q(X) a [conjunctive_query_full], if every relation contains at most m tuples, then the size of the query result is at most m^{f} for f the [fractional_edge_cover] of Q 4 5 Only works with [cardinality_constraint], not with [degree_constraint] 6 7 - AGM bound with [projection]: [gottlob2012size] 8 9 Lower bound: [agm_lower_bound] 10 11 Remark by [mahmoud_abo_khamis]: the reverse of AGM bound is [turan_theorem], largest graph to avoid a pattern 12 - remark that if you fix the number of vertices of a graph then if the number of edges is larger than some value then there must be a [triangle] 13 - the bound turns out to be the number of edges in a [graph_bipartite] on this set of vertices 14 - cf [ramsey_theorem] also? 15 16 See also: [optimal_joins], [heavy_light] 17 18 Up: [computer_science] 19 20 Tags: #wikipedia