Delphi.science

Classification of Forbidden 0-1 Patterns by Their Extremal Function

Source: arxiv.org/abs/2611.23333

Jesse Geneson, Seth Pettie

arXivarxiv/2611.23333Nov 16, 2026math.COscore 0

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.…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'