ProofAtlas

Extremal graph theory · bipartite graphs · finite geometry

Zarankiewicz Problem

Collaboration beta

How many edges can a bipartite graph have while avoiding one fixed complete bipartite pattern?

z(n,n;s,t)=Θs,t(n2-1/s)for every fixed2≤s≤t
Known results and sources
Two opposing shores of vertices are joined by a dense field of cross-edges, with one amber rectangular gap marking the forbidden complete bipartite pattern.
The Zarankiewicz problem asks how dense a bipartite graph can be while avoiding a fixed complete bipartite subgraph.

Research problem

Exact mathematical statement

For fixed integers 2≤s≤t2\le s\le t, let z(m,n;s,t)z(m,n;s,t) be the maximum number of edges in a bipartite graph with parts of sizes m,nm,n that contains no Ks,tK_{s,t}, with the ss-vertex side in the first part and the tt-vertex side in the second. The balanced target asks whether

z(n,n;s,t)=Θs,t(n2-1/s)for every fixed2≤s≤t.z(n,n;s,t)=\Theta_{s,t}\left(n^{2-1/s}\right) \qquad\text{for every fixed }2\le s\le t.

The classical Kővári–Sós–Turán theorem supplies the upper-order bound. Matching lower bounds for the full fixed-parameter family remain open. A construction only for s=4s=4, or on isolated field sizes without an all-size bridge, would not close this target.

Problem infographic

Problem at a glance

A deterministic explainer defines z(m,n;s,t), shows the four-edge K2,2 forbidden rectangle, and displays the exact 7-by-7, 21-edge Fano-plane incidence graph as a K2,2-free example beside the still-open balanced asymptotic target.
The smallest forbidden rectangle is K2,2; denser K2,2-free examples exist, but the matching asymptotic lower bound for every fixed 2≤s≤t remains open.

Current mathematical picture

Where work on Zarankiewicz Problem stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failurePositive-density vector Reed–Solomon parent macroassembly

The current work's RS-PCORE-CLOSURE theorem rules out arbitrary positive-density parents and explicitly closes the original polynomial-core macroassembly route. Characteristic-two exterior tensors, nonlinear or additive MDS packing, semilinear directional-jet constructions, and the characteristic-three first-hard-case program remain live within their stated scopes.

Route status · Narrowed route
Main reductionBounded-gap all-size bridge

The source reports that endpoint constructions along a bounded-multiplicative-gap field-size sequence pad to every sufficiently large n.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeComplete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum.Task status · Ready to work on

Work mapped so far

Zarankiewicz Problem in numbers

1.1kretained lines of mathematical investigation1,054 in the current working snapshot
Argument development
883 · 84%
Explored or eliminated routes
29 · 3%
Computational analysis
39 · 4%
Open obligations
48 · 5%
Definitions and setup
55 · 5%
7selected mapped statements2routes investigated5open questions5contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byKazimierz ZarankiewiczProposed1951Status checkedAug 27, 2026
Source recordedAug 27, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

14 selected steps

Scroll horizontally to explore the route

Working route overview for Zarankiewicz ProblemA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.The balanced K_{s,t}-free extremal edge count should match the classical upper-bound exponent for every fixed parameter pair. — Depends on missing premiseThe balanced K_{s,t}-freeextremal edge count shouldmatch…Bounded-gap all-size bridge — Depends on missing premiseBounded-gap all-size bridgeCurrent reduction — Depends on missing premiseCurrent reductionEndpoint block-packing interface — Depends on missing premiseEndpoint block-packinginterfaceClosing target — Depends on missing premiseClosing targetFinite q=3 quadratic seed — Depends on missing premiseFinite q=3 quadratic seedVector Reed–Solomon parent closure — Depends on missing premiseVector Reed–Solomon parentclosurePositive-density vector Reed–Solomon parent macroassembly — stoppedPositive-density vectorReed–Solomon parentmacroassemblyFinite-seed extrapolation — stoppedFinite-seed extrapolationComplete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum. — OpenComplete thecharacteristic-twostratified…Prove an MDS transition dichotomy separating expanding transition systems from bounded-complexity invariant geometry. — OpenProve an MDS transitiondichotomy separatingexpanding…Construct a nonlinear dimension-s MDS family containing enough dense nested MDS boxes with the required global intersection rule. — OpenConstruct a nonlineardimension-s MDS familycontaining…All-stratum characteristic-two tensor construction — OpenAll-stratumcharacteristic-two tensorconstructionNonlinear MDS nested-box construction — OpenNonlinear MDS nested-boxconstruction
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routePositive-density vector Reed–Solomon parent macroassembly

The current work's RS-PCORE-CLOSURE theorem rules out arbitrary positive-density parents and explicitly closes the original polynomial-core macroassembly route. Characteristic-two exterior tensors, nonlinear or additive MDS packing, semilinear directional-jet constructions, and the characteristic-three first-hard-case program remain live within their stated scopes.

Route status · Narrowed route
Narrowed routeFinite-seed extrapolation

The current work requires a symbolic field-family identity and a bounded-gap size theorem; finite success or failure alone does not settle an asymptotic route. Retain verified finite instances as narrow testbeds and promote them only after their exact model, complete candidate class, quantifiers, verifier or certificate, log digest, and asymptotic implication are established.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks
01
Complete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum.Suggested move: Classify shift-set orbits by affine rank, compute exact stratum data, test Moore-type condensers, derive stronger collision controls on silent strata, prove rank statements symbolically, and reconcile all equality-stratum Fourier equations.
Ready to work on
02
Prove an MDS transition dichotomy separating expanding transition systems from bounded-complexity invariant geometry.Suggested move: Define information-set-independent transition operators, connect nonexpansion to common projective Fourier packets, prove an inverse theorem, and count local states in every invariant-geometry outcome.
Ready to work on
03
All-stratum characteristic-two tensor construction

No tensor is known to satisfy every nontrivial exterior contraction while separately controlling silent higher-rank strata and the global equality-stratum completion.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Nonlinear MDS nested-box construction

The current work retains the search for a nonlinear dimension-s MDS family with enough nested dense boxes satisfying the global intersection rule.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
05
Construct a nonlinear dimension-s MDS family containing enough dense nested MDS boxes with the required global intersection rule.Suggested move: Search switched MDS codes, quasigroup products, and coordinatized orthogonal arrays for exact box-intersection structures, not merely examples inequivalent to linear Reed–Solomon codes.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 27, 2026
Current statusOpen problem

The general ordered-part Zarankiewicz problem remains open. The classical upper-order bound and matching results in selected parameter ranges or restricted graph classes do not supply the full balanced Θ_{s,t}(n^{2−1/s}) conclusion for every fixed 2≤s≤t.

[3][4][5]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. PreprintA modern paper recorded progress for restricted geometric classes while explicitly keeping the general problem open.[5]
  2. PreprintThe official arXiv submission history records v1 on 2024-09-24; the 2410 announcement identifier does not override that exact history. The survey described the general bipartite extremal asymptotics as widely open and surveyed geometric variants.[4]
  3. Peer reviewedConlon proved that the classical upper bound is tight up to the constant for a broad parameter range, without closing the full fixed-parameter family.[3]
  4. Peer reviewedKővári, Sós, and Turán established the classical general upper-bound method for the problem.[2]
5 cited sources4 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusZarankiewicz problem
Dependency or reductionKővári–Sós–Turán theorem

The Kővári–Sós–Turán theorem supplies the foundational general upper bound.

[2]
Equivalent formulationforbidden all-one submatrix problem

The ordered-part graph problem is equivalent to maximizing ones in a zero-one matrix with no all-one rectangular submatrix.

[3]
Solved special casegeometric Zarankiewicz problems

Geometrically defined and other restricted graph classes admit sharper results but do not settle the unrestricted family.

[4][5]
Related problemC4-free bipartite graphs

The s=t=2 specialization is the C4-free bipartite extremal problem.

[3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA statement-aligned formalization must define ordered bipartite part sizes, K_{s,t} exclusion with the oriented s-side convention, the extremal edge count z(m,n;s,t), and the fixed-parameter balanced asymptotic quantifiers.
  • Formalization targetThe Kővári–Sós–Turán upper bound must remain distinct from the missing matching lower bound.
  • Formalization targetFinite examples and restricted graph classes must remain distinct from the all-fixed-s,t asymptotic target.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements5 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction2 of 72
  • lemma1 of 71
  • equivalence1 of 71
  • negative result1 of 71
  • computational claim1 of 71
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementThe balanced K_{s,t}-free extremal edge count should match the classical upper-bound exponent for every fixed parameter pair.
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementEndpoint block-packing interfaceintermediate
  • retained route statementBounded-gap all-size bridgeintermediate
  • retained route statementVector Reed–Solomon parent closureintermediate
  • retained route statementFinite q=3 quadratic seedintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failurePositive-density vector Reed–Solomon parent macroassemblyreported failure
  • Useful failureFinite-seed extrapolationreported failure
  • Research targetComplete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum.open
  • Research targetProve an MDS transition dichotomy separating expanding transition systems from bounded-complexity invariant geometry.open
  • Research targetConstruct a nonlinear dimension-s MDS family containing enough dense nested MDS boxes with the required global intersection rule.open
  • Research targetAll-stratum characteristic-two tensor constructionopen
  • Research targetNonlinear MDS nested-box constructionopen
  • ComputationThe current work lists five packaged exact scripts, including a q=3 nondegenerate quadratic K_{4,4}-free seed and finite obstructions or censuses in sharply limited models.ProofAtlas did not run any submitted script during intake. Every finite result remains source-reported evidence at its displayed finite scope, and missing post-v2 artifacts remain noncontrolling. · reported unreproduced
  • Narrowed routePositive-density vector Reed–Solomon parent macroassemblyThe current work's RS-PCORE-CLOSURE theorem rules out arbitrary positive-density parents and explicitly closes the original polynomial-core macroassembly route. Characteristic-two exterior tensors, nonlinear or additive MDS packing, semilinear directional-jet constructions, and the characteristic-three first-hard-case program remain live within their stated scopes.
  • Narrowed routeFinite-seed extrapolationThe current work requires a symbolic field-family identity and a bounded-gap size theorem; finite success or failure alone does not settle an asymptotic route. Retain verified finite instances as narrow testbeds and promote them only after their exact model, complete candidate class, quantifiers, verifier or certificate, log digest, and asymptotic implication are established.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeComplete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointComplete the characteristic-two stratified tensor program for s=6 and s=7 across every nontrivial and silent shift stratum.

Zarankiewicz Problem · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

How many edges can a bipartite graph have while avoiding one fixed complete bipartite pattern?

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references5 cited works · next context review by Nov 27, 2026

The mathematical context was checked on Aug 27, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Problem P 101 (in PROBLÈMES, vol. 2, fasc. 3–4)original source · Kazimierz Zarankiewicz · Colloquium Mathematicum · 1951 · accessed Aug 27, 2026
  2. 2
    On a problem of K. Zarankiewiczpeer reviewed result · Tamás Kővári, Vera T. Sós, Pál Turán · Colloquium Mathematicum · 1954 · DOI 10.4064/cm-3-1-50-57 · accessed Aug 27, 2026
  3. 3
    Some remarks on the Zarankiewicz problempeer reviewed result · David Conlon · Mathematical Proceedings of the Cambridge Philosophical Society · 2021 · ARXIV 2007.12816 · DOI 10.1017/S0305004121000475 · accessed Aug 27, 2026
  4. 4
    A survey of Zarankiewicz problem in geometrysurvey or monograph · Shakhar Smorodinsky · arXiv · 2024-09-24 · ARXIV 2410.03702 · accessed Aug 27, 2026
  5. 5
    C4-free subgraphs of high degree with geometric applicationspreprint · Zach Hunter, Aleksa Milojević, István Tomon, Benny Sudakov · arXiv · 2025-06-30 · ARXIV 2506.23942 · accessed Aug 27, 2026

Important qualifications

  • The bounded direct-source review establishes a conservative identity and current-status baseline, not an exhaustive history of every parameter range.
  • Recent geometric and other restricted-class results do not establish the full ordered-part asymptotic target.
  • No submitted packet URL or attachment was used as independent external status authority.
  • No statement-aligned formalization or independently reproduced packet computation was established by this scoped search.
  • This extremal-edge problem is distinct from the Zarankiewicz crossing-number conjecture.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image