Classification of Forbidden 0-1 Patterns by Their Extremal Function
Source: arxiv.org/abs/2611.23333
This paper concerns the maximum weight of $n\times n$ 0-1 matrices that avoid some pattern $P$, denoted $\operatorname{ex}(n,P)$. Furedi and Hajnal initiated a research program of classifying all patterns according to their extremal function, but to date, only the weight-4 patterns are completely understood. In this paper we make progress on several fronts of the classification problem. A pattern is light if its columns have weight 1 and linear if $\operatorname{ex}(n,P)=O(n)$. We characterize the set of weight-5 linear light patterns, and the set of weight-5 linear patterns more generally.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.23333
curl -X POST /api/v1/records/arxiv/2611.23333/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.23333/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'