What makes a plausible research argument checkable by someone else?
A mathematical claim becomes checkable when a reader can recover its objects, hypotheses, quantifiers, evidence, and logical steps without guessing what the author intended. A convincing picture may suggest a claim; a proof must explain why every permitted instance satisfies it. A successful reproduction also identifies what belongs to earlier work and what the reproducer has added.
Our running example concerns a binary matrix, whose entries are either zero or one. Write $A=(a_{rc})$ for a matrix with $R$ rows and $C$ columns. An increasing pair consists of two ones at positions $(r,c)$ and $(s,d)$ with $r\lt s$ and $c\lt d$. Avoiding an increasing pair is equivalent to avoiding the two-by-two identity pattern $I_2$ under ordered, non-induced containment: choose two rows and columns in their original order, require the two diagonal entries to be one, and allow either value at the other entries.
Partition the rows into consecutive intervals and do the same for columns. Replace each resulting block by one if it contains any one, and by zero otherwise. Call the resulting matrix $B$ the occupancy compression of $A$. The claim we will reproduce is that if $A$ avoids a permutation pattern, then $B$ avoids that pattern too. The foundation needs only the case $I_2$: a diagonal pair in two distinct compressed blocks lifts to an increasing pair in the original matrix because both row order and column order are preserved.
The final investigation supplies the general proof and a complete manuscript outline, so the numbered sections are optional extensions. The prerequisite, experimental and computational combinatorics, explains exhaustive searches and certificates. Here we ask how to turn those habits into a research argument another person can audit.
What makes a plausible research argument checkable by someone else?
A fully specified instance. Use rows and columns numbered from one:
$$ A=\begin{pmatrix} 0&0&1&1\\ 0&0&1&0\\ 1&1&0&0\\ 1&0&0&0 \end{pmatrix}. $$
Take row intervals $\{1,2\},\{3,4\}$ and the same column intervals. Reading the four blocks in row order gives occupancies $0,1,1,0$, hence
$$B=\begin{pmatrix}0&1\\ 1&0\end{pmatrix}.$$
The compressed matrix has no increasing pair. To verify the original matrix independently, inspect its six ones. Within the upper-right block, the only later-row one is in column three, which is not larger than any earlier occupied column. The analogous statement holds in the lower-left block. Across the two blocks, later rows have smaller columns. Thus $A$ also avoids $I_2$.
Question to revisit. Does the conclusion reverse? No: put two ones at $(1,1)$ and $(2,2)$ in an otherwise zero four-by-four matrix. They lie in the same block, so its compression has just one occupied cell and avoids $I_2$, while the original contains it. We need a proof of the forward implication and a record of this counterexample to the reverse implication.
55.1 How to read a research paper in combinatorics
Optional extension; not required to complete the chapter foundation.
Read first for the question, then for the definitions, then for the dependency of one result on another. A claim ledger is a short record of each statement you intend to use: its exact hypotheses, conclusion, source location, and proof status. A dependency is an earlier statement needed to justify a later one. The ledger prevents a memorable abstract from silently replacing a precise theorem.
Use Adam Marcus and Gábor Tardos, Excluded permutation matrices and the Stanley–Wilf conjecture, as a primary reading. Its opening definition preserves row and column order and permits extra ones. Its Lemma 4 concerns occupancy compression. Theorem 1 establishes a linear extremal bound for each fixed permutation pattern; reproducing the compression lemma alone does not reproduce that theorem. The author-hosted copy is dated November 2003; distinguish that preprint date from the 2004 journal publication.
Solved reading example. Suppose your notes say, “Every pattern survives compression.” Compare this sentence with the definition and hypotheses. A permutation matrix has exactly one one in each row and column, and the source works with consecutive blocks. Your sentence omits both restrictions and confuses the direction: an occurrence in the compressed matrix lifts to the original. Replace it with a statement of that implication. Its contrapositive then gives preservation of avoidance.
For a general $k$-by-$k$ permutation matrix $P$, write its unique one in row $i$ as column $\pi(i)$; the map $\pi$ permutes $\{1,\ldots,k\}$. This notation describes precisely which compressed cells must be occupied. Keep the original proof beside your reconstruction until each use of order, distinctness, and existence is accounted for. Then close the source and write the argument independently.
Exercise. Does the all-one two-by-two matrix contain $I_2$ under our definition? Hint: distinguish containment from equality. Solution: yes. Its diagonal entries are one, and the extra off-diagonal ones are allowed. An implementation demanding exact equality would check a different problem.
Read a result as a quantified statement with explicit hypotheses, not as a slogan. For occupancy compression, the lifting argument depends on ordered blocks and distinct pattern rows and columns; a successful finite test does not replace either hypothesis or the general proof.
55.2 Literature reviews and citation trails
Optional extension; not required to complete the chapter foundation.
A literature review organizes mathematical claims and their relationships, rather than listing papers by date. A citation trail follows references backward to the source of a definition or result and follows later papers forward to corrections, generalizations, or new proofs. A bibliographic record identifies authors, title, version or publication, stable link, and the location of the particular result being used.
Separate three questions: “Where did I learn this?”, “Where was it proved?”, and “Which statement am I actually relying on?” A lecture note may answer the first while a research paper answers the second. Versions can change numbering and hypotheses, so record the version you inspected. A search result is a discovery aid; read the primary statement before attaching its citation to your claim.
Literature reviews and citation trails: a worked example
Question: what should a manuscript reproducing occupancy compression cite?
| Proposed statement | Evidence to inspect | Safe conclusion |
|---|---|---|
| Ordered containment permits extra ones | Opening definition in Marcus–Tardos | State that definition explicitly |
| Compression preserves permutation-pattern avoidance | Lemma 4 and its preceding block construction | Attribute the lemma; explain any changed block sizes |
| This reproduction proves the full extremal theorem | The dependency chain beyond Lemma 4 | Reject: additional lemmas are needed |
| Exhaustive four-by-four testing is new mathematics | Search for previous computations and formulations | Record a reproducibility exercise; claim no novelty without evidence |
The worked result is a reading record, not a claim of priority: “We reproduce the occupancy argument from Lemma 4 and check its $I_2$ specialization for all four-by-four binary matrices.” Our version allows unequal consecutive intervals. That generalization of the formulation follows from the same order argument; do not describe it as a novel theorem merely because the source uses equal blocks in its application.
Assumption check: the matrix is binary, containment is ordered and non-induced, the pattern is a permutation matrix, and the row and column groups are consecutive intervals. All four conditions appear either in the definition or in the recorded setup.
Exercise. A later paper cites a lemma with a similar name but studies induced containment. Can it support your non-induced statement without further work? Hint: compare permitted extra entries. Solution: no. Read its definitions and establish a translation if one exists. Similar vocabulary does not establish equivalence.
Make the review actionable by recording one unresolved reading question per source. For this chapter, that question might be why the full extremal proof needs information about the distribution of ones inside blocks after occupancy has discarded that information. A good review identifies the missing ingredient rather than presenting a disconnected bibliography.
55.3 Understanding assumptions and proof techniques
Optional extension; not required to complete the chapter foundation.
A hypothesis audit asks where each assumption enters the argument. A witness is a concrete object establishing an existential assertion; for matrix containment it is a list of selected rows and columns. A lifting argument transforms a witness in a simpler object into a witness in the original object. The critical issue is whether individually valid choices can satisfy the required relationships simultaneously.
Solved example: why arbitrary binary patterns fail. Let $Q$ be the one-by-two pattern $(1\;1)$, and let $A=I_2$. No row of $A$ has two ones, so $A$ avoids $Q$. Merge both rows into a single interval and leave the two columns separate. The compression is $B=(1\;1)$ and contains $Q$. Choosing a one from each occupied block picks different original rows. The two choices therefore fail to form the single row required by $Q$.
The diagram displays exactly this counterexample. Filled cells contain one; empty cells contain zero. The merged row interval includes both original rows. The two column intervals remain separate, so both compressed cells are occupied. The orange labels identify the missing shared-row condition, rather than suggesting that the valid permutation lemma fails.
Consecutiveness also matters for preserving order. If you replace intervals by arbitrarily interlaced groups, their group labels need not match the order of the chosen original indices. For example, $A$ with ones at $(1,2)$ and $(2,1)$ avoids $I_2$. Declare the first row group to be $\{2\}$ and the second $\{1\}$ while keeping column order. Compression becomes $I_2$. This is a reordered partition, outside the permitted construction.
Exercise. For $A=I_2$, compress all rows and all columns into one block. What information disappears? Hint: compare the dimensions required for an increasing pair. Solution: the output is the one-by-one matrix $(1)$. It contains no increasing pair; the original does. Compression loses multiplicity and the relative positions of ones inside a block, explaining why the reverse implication fails.
55.4 Reproducing classical proofs
Optional extension; not required to complete the chapter foundation.
A proof reproduction rebuilds a published argument with its dependencies and hypotheses intact. It can expand implicit steps, repair your own misunderstandings, and provide a clearer finite example without claiming a new result. Begin with a lemma small enough to verify completely. Do not replace an unfamiliar step with “obvious”; identify the missing assertion and prove it or label it as an omitted prerequisite.
Complete proof of the $I_2$ compression case. Suppose $B$ contains ones in compressed positions $(i,j)$ and $(u,v)$ with $i\lt u$ and $j\lt v$. Let $X_i,X_u$ be their row intervals and $Y_j,Y_v$ their column intervals. Occupancy supplies ones $a_{rc}=a_{sd}=1$ with $r\in X_i$, $s\in X_u$, $c\in Y_j$, and $d\in Y_v$. Every index of $X_i$ precedes every index of $X_u$, so $r\lt s$. Similarly $c\lt d$. Thus these original ones form an increasing pair. Taking the contrapositive proves that $I_2$-avoidance passes to $B$.
Solved witness example. In a four-by-four matrix with ones at $(2,1)$ and $(3,4)$ and zeros elsewhere, the usual two-by-two blocks yield ones at compressed positions $(1,1)$ and $(2,2)$. Lift them to the stated original cells. Check $2\lt3$ and $1\lt4$. These four numbers are a certificate of containment that a reader can verify without rerunning a search.
A faithful reconstruction separates the source's specialized setup from the mechanism. Equal block sizes are unnecessary for this lifting step; nonempty ordered intervals suffice. Conversely, this relaxation says nothing about later estimates that use equal block sizes. The source may impose a condition for the larger argument even when one lemma does not need it.
Exercise. Does the proof require the two lifted ones to have been chosen by a particular rule, such as choosing the upper-leftmost one? Hint: inspect which inequalities depend on their positions inside blocks. Solution: no. Any one in each witness block works because the distinct intervals determine strict row and column order. A deterministic choice rule is useful for reproducible certificates, but is not needed for existence.
55.5 Reconstructing computational results
Optional extension; not required to complete the chapter foundation.
A computational reconstruction specifies the instance space, encoding, predicates, enumeration order, outputs, and independent checks. For an $n$-by-$n$ binary matrix, encode its entries by a nonnegative integer $m\lt2^{n^2}$, taking the bit at position $(r-1)n+c-1$ to be $a_{rc}$. Each possible matrix then occurs exactly once. This definition is part of the experiment, not an implementation detail to leave unstated.
Solved exhaustive experiment. For each $m$, decode the matrix and test whether any ordered row pair and ordered column pair give two diagonal ones. The predicate tests $\binom n2^2$ candidates and allows arbitrary off-diagonal entries. Count avoiding matrices, and record the largest number of ones among them. The complete outputs for $n=1,2,3,4$ are:
| Size $n$ | Matrices tested | Matrices avoiding $I_2$ | Maximum number of ones |
|---|---|---|---|
| 1 | 2 | 2 | 1 |
| 2 | 16 | 12 | 3 |
| 3 | 512 | 104 | 5 |
| 4 | 65,536 | 1,008 | 7 |
For every four-by-four matrix avoiding $I_2$, also form its two-by-two occupancy compression. All 1,008 such matrices produce a compression avoiding $I_2$; there are zero violations. The histogram of their numbers of ones, indexed from zero through seven, is $1,16,84,216,309,252,110,20$. Its sum is 1,008, providing an additional output check.
The experiment is deterministic and uses exact integer operations, so no sampling confidence interval applies. A straightforward streaming implementation takes $O(2^{n^2}n^4)$ time and $O(n^2)$ working memory, aside from stored results. It is appropriate for these small sizes and becomes infeasible rapidly. Record the interpreter version, source bytes, invocation, and output in a reproducibility package; do not invent a runtime measurement you have not taken.
Check the increasing-pair predicate against a second formulation: for each one at $(r,c)$, ask whether the strictly lower-right submatrix contains a one. Test the zero matrix, all-one matrix, both two-by-two permutation matrices, and the reverse-implication counterexample before trusting aggregate counts. A mismatch must be resolved before either output is cited.
Exercise. A program examines only permutation matrices. Does it validate the table? Hint: compare $n!$ with $2^{n^2}$. Solution: no. Permutation matrices are a small subset of the binary instance space. Such a program could test permutation avoidance, but it would omit matrices with repeated or empty occupied rows and columns. The finite experiment supports the lemma on its enumerated inputs; the general proof supports all dimensions.
55.6 Identifying special cases of open problems
Optional extension; not required to complete the chapter foundation.
A special case restricts the hypotheses or the family of objects while retaining the intended conclusion. Its value depends on whether the restriction exposes a mechanism and whether the result is already known. A finite verification, an infinite family, and a solution of the unrestricted problem are different achievements. Before choosing a project, write the full quantifier order and search for results covering the proposed restriction.
For a graph $G$, let $\alpha(G)$ be the largest independent-set size and $\omega(G)$ the largest clique size. A graph is $H$-free here if it has no induced copy of the fixed graph $H$. The Erdős–Hajnal conjecture asks whether for every $H$ there exists $\delta_H>0$ such that every $H$-free graph on $n\ge1$ vertices satisfies
$$\max\{\alpha(G),\omega(G)\}\ge n^{\delta_H}.$$
Dated status, checked 13 October 2026: Huang, Ju, and Zhou's 2026 primary preprint, version 3 treats the general assertion as open and reports further special cases. It also records that all five-vertex cases are known following recent progress. This chapter uses a much simpler, already established case as training; it makes no claim that a particular larger graph is a new open target. Recheck current primary literature when selecting an actual research problem.
Solved special case: $H=P_3$, the three-vertex path. Every connected component of a $P_3$-free graph is a clique. Otherwise two nonadjacent vertices in a component admit a shortest path of length at least two. Its first three vertices induce $P_3$: the first and third cannot be adjacent, since that would shorten the path. This contradicts the hypothesis.
Let $t$ be the number of components and $s$ the largest component size. Selecting one vertex from each component gives an independent set of size $t$, while the largest component gives a clique of size $s$. Since $n\le ts$, at least one of $t,s$ is at least $\sqrt n$. Thus the claimed property holds with $\delta_{P_3}=1/2$. This is an infinite-family proof, not merely testing a few graphs.
Exercise. Construct a nine-vertex $P_3$-free graph with $\alpha(G)=\omega(G)=3$. Hint: use equally sized complete components. Solution: take three disjoint triangles. This attains the square-root bound and shows that no larger exponent works uniformly for this case: $t$ disjoint copies of $K_t$ have $n=t^2$ and both parameters equal to $t$.
The advanced proofs behind current larger special cases are omitted prerequisites; this section does not reproduce them. The project-selection lesson is to solve an accessible case independently, then audit the literature before describing its novelty or its relationship to the open remainder.
55.7 Proving partial results and structural lemmas
Optional extension; not required to complete the chapter foundation.
A structural lemma identifies a constraint shared by every object satisfying certain hypotheses. A partial result establishes a restricted conclusion or a restricted family rather than the whole target. A useful lemma explains why many examples behave similarly and may suggest an efficient verification method.
We now prove an exact bound suggested by the computational table. If a binary $R$-by-$C$ matrix avoids $I_2$, then it has at most $R+C-1$ ones, for positive integers $R,C$. Index each cell by the integer $r-c$. There are exactly $R+C-1$ possible values, from $1-C$ through $R-1$. On any fixed diagonal $r-c=d$, two distinct cells have both row and column increasing together. They cannot both be one in an avoiding matrix. At most one one per diagonal proves the bound. This is a complete proof, with no asymptotic or computational prerequisite.
The bound is attained: fill every cell of the first row and every cell of the first column, leaving the rest zero. The shared cell $(1,1)$ is counted once, so there are $R+C-1$ ones. Any later-row one lies in column one, preventing it from being strictly southeast of an earlier one. Thus the construction avoids $I_2$ and the bound is exact.
Solved instance. For $R=3,C=4$, there are six diagonals, and the first-row/first-column construction has $4+3-1=6$ ones. This proves the extremal value for every three-by-four matrix; there is no need to enumerate all $2^{12}$ possibilities to establish that value.
The proof uses a partition of cells into chains under strict southeast order. It converts a forbidden pair into a capacity constraint of one per chain. In a larger project, ask whether a comparable partition exists for a different pattern. That is a research direction to investigate, not a theorem established here. For general permutation patterns, the exact diagonal argument above does not supply the full bound.
Exercise. What bound follows for a five-by-seven matrix avoiding $I_2$? Give an attaining example. Hint: count possible values of $r-c$. Solution: at most eleven ones; all seven entries in the first row together with the four remaining entries in the first column attain eleven. A manuscript should include both upper bound and construction when using the word “exact.”
55.8 Building conjectures from examples
Optional extension; not required to complete the chapter foundation.
A conjecture is a proposed statement not yet proved in the context under discussion. An experimental pattern is a regularity observed in computed instances. To develop a conjecture responsibly, specify its quantifiers, seek adverse cases, and maintain a log distinguishing refuted, proved, and unresolved statements. Updating a conjecture after a counterexample should change the written claim, not merely add an unexplained exception.
Solved conjecture cycle. The maxima $1,3,5,7$ suggest the tentative statement that every $n$-by-$n$ matrix avoiding $I_2$ has at most $2n-1$ ones. The diagonal proof in Section 55.7 turns that tentative statement into a theorem and establishes attainment. From that point onward, label it a theorem in the local project, even if the notebook retains an earlier entry headed “conjecture.” No novelty is claimed for this elementary result.
A second plausible guess says, “An avoiding matrix must have a row or column containing all its ones.” The two-by-two matrix with ones at $(1,2)$ and $(2,1)$ refutes it. Those ones have reversed column order and do not form an increasing pair, but share neither a row nor a column. The weaker diagonal constraint survives this test and admits a proof.
Finite counts can also tempt an unjustified enumeration formula. Four values do not determine a sequence: many rules agree at $n=1,2,3,4$ and disagree later. Before fitting a formula, inspect whether the objects decompose into smaller objects with a unique reconstruction. That supplies a possible recurrence rather than just a numerical fit. Any proposed recurrence still needs a proof covering both construction and uniqueness.
Exercise. A search for increasing pairs found none in 10,000 randomly generated matrices that passed a filter. What can be concluded? Hint: ask whether the filter already enforces avoidance and whether the sample covers all matrices. Solution: only the recorded sample result follows. The filter may have selected a narrow or even tautological family. Specify the sampling distribution and predicate; do not promote the result to a universal theorem.
For open-ended extensions in this chapter, use “investigation question” rather than “open problem” unless current literature establishes the latter status. An uncertainty in your understanding is not automatically an uncertainty in mathematics.
55.9 Writing rigorous mathematical proofs
Optional extension; not required to complete the chapter foundation.
A rigorous proof fixes the domain, states the claim, introduces each object before use, and justifies every passage from hypotheses to conclusion. An existential witness must satisfy all the required conditions simultaneously. The words “choose arbitrary” are justified only if every permitted choice works; otherwise describe how the choice is made.
Solved repair. A draft reads: “Pick one from each block. These form the pattern.” Its gap is that the selected cells might not share or preserve the required rows and columns. For a permutation pattern, repair it as follows. Suppose $B$ contains $P$, whose row-$i$ one lies in column $\pi(i)$. Let the selected compressed row indices be $u_1\lt\cdots\lt u_k$ and selected column indices be $v_1\lt\cdots\lt v_k$. For each $i$, choose a one from original block $(u_i,v_{\pi(i)})$.
The row coordinates of these choices increase with $i$ because they belong to distinct ordered row intervals. Their column coordinates are distinct; their relative order agrees with $\pi(i)$ because they belong to distinct ordered column intervals. Sort those coordinates into selected original columns. The chosen ones then occur exactly at the positions required by $P$; any additional ones are permitted. Thus $A$ contains $P$. This proves the lifting implication and, by contraposition, the avoidance implication. This is a complete argument, not a proof sketch.
Avoid a hidden change in quantifiers. The statement is about every binary matrix and every permitted interval partition for a fixed permutation pattern. A computational record involving one partition and one pattern is a smaller claim. Likewise, a bound with a constant depending on a fixed pattern does not assert a single constant uniform across all pattern sizes.
Exercise. Rewrite “If compression has no occurrence, neither does the original” as a proposed implication, then decide its truth. Hint: use the one-block counterexample. Solution: the proposed implication is $B\text{ avoids }P\Rightarrow A\text{ avoids }P$. It is false for $P=I_2$. The proved implication is $A\text{ avoids }P\Rightarrow B\text{ avoids }P$, whose contrapositive is $B\text{ contains }P\Rightarrow A\text{ contains }P$.
A final proof pass should remove ambiguous pronouns, check the empty or boundary cases, and ensure every referenced lemma has its hypotheses verified where used. For our lemma, if the compressed matrix has fewer than $k$ rows or columns, containment is impossible and the avoidance conclusion is immediate. The witness proof covers all other cases without assuming equal interval lengths.
55.10 Preparing a research manuscript and seminar presentation
Optional extension; not required to complete the chapter foundation.
A manuscript is an argument organized for readers to assess its claims and evidence. A seminar presentation is a guided route through the same argument, with time devoted to motivation, definitions, one decisive mechanism, and limitations. A contribution statement explains what the work adds. For this project, the contribution is an educational reproduction with explicit assumptions and a finite audit; it is not a newly discovered compression theorem.
Solved manuscript plan. Use the title “An explicit reproduction of occupancy compression for permutation patterns.” The abstract should identify the attributed lemma, the interval formulation, the exhaustive $I_2$ test through four-by-four matrices, and the counterexamples delimiting scope. The introduction poses the question of what compression preserves. Definitions fix containment and occupancy. The main result gives the complete witness-lifting proof. The experiment records the encoding, predicates, counts, and independent verification. A final discussion states exactly what was proved and what information compression loses.
Use numbered statements only when you reference them, and place examples near the definition they clarify. A citation should identify a specific result when possible. A data-availability paragraph should point to the actual script and outputs supplied with a real manuscript; it should not promise unavailable files or claim an independent replication that nobody performed.
For a twelve-minute seminar, allocate two minutes to the compression question and example, two to definitions, four to lifting one witness and explaining the permutation condition, two to counterexamples, and two to the finite audit and conclusion. This totals twelve minutes. Show the full theorem statement before the proof and keep the worked witness visible while explaining why the original coordinates are ordered. The audience should be able to state the implication's direction afterward.
Publication adds a separate assessment of originality, correctness, and fit. Discuss authorship and contributions with actual collaborators, choose a suitable venue, and read its current instructions. A preprint announcement and journal peer review have different roles. As checked on 13 October 2026, the official arXiv submission guidance describes its submission workflow; consult that current guidance rather than relying on a remembered procedure. This exercise prepares a manuscript and talk, not a submission.
Exercise. Repair the abstract sentence, “We prove a new theorem by checking 65,536 matrices.” Hint: separate attribution, proof, and experiment. Solution: “We reproduce a published compression lemma with an explicit witness-lifting proof and audit its $I_2$ specialization on all 65,536 four-by-four binary matrices.” This sentence identifies what is established and how, without inventing novelty.
Reproduce a lemma and write a short research manuscript
The investigation joins careful paper reading to a reviewable mathematical product. You will reproduce one lemma, write a complete proof, delimit its scope with counterexamples, and report an exhaustive finite experiment. The opening definitions and the solution outline below supply the foundation; the numbered extensions offer additional research practice.
The cross-disciplinary connection is to ordered event tables. Let rows represent time slots and columns represent resource positions; a one records an event. An increasing pair means an event at a later time and a larger resource index. If such a pair is forbidden, interval aggregation cannot create one: any coarse witness would lift to actual events. This can justify a coarse screening step. A negative coarse result cannot certify the original table's avoidance, because a violation may occur inside one aggregated block. The application follows the exact implication proved here.
Reproduce a lemma and write a short research manuscript
Inputs and hypotheses. Read the opening matrix definition and Lemma 4 in the linked Marcus–Tardos paper. Work with a fixed $k$-by-$k$ permutation matrix $P$, a binary $R$-by-$C$ matrix $A$, and partitions into nonempty consecutive row and column intervals, listed in their original order. Define each entry of the compressed matrix $B$ to be one exactly when its corresponding block contains a one.
Deliverable 1: warm-up and claim ledger, 15 points. Compute the opening four-by-four compression and list its six original ones. Record the source lemma, the chosen containment convention, all hypotheses, and the exact direction of the implication. Distinguish the source's block setup from the interval formulation used here.
Deliverable 2: a complete proof, 30 points. Prove that $A$ avoiding $P$ implies $B$ avoiding $P$. Hint: first prove the contrapositive by lifting the occupied cells in a compressed occurrence. Explain why the selected original rows are distinct and ordered, why the selected columns are distinct and have the required order, and why extra ones do not invalidate containment.
Deliverable 3: scope checks, 15 points. Give explicit counterexamples to the reverse implication and to allowing two pattern ones in one row. For each, write both matrices and exhibit the occurrence or explain its absence. Describe how disregarding the original order of groups can also break the conclusion.
Deliverable 4: finite audit, 20 points. Enumerate every four-by-four binary matrix by the stated bit encoding. Report the number avoiding $I_2$, the weight histogram, and any violation of the compression implication for the two-by-two interval partition. Verify the containment predicate independently using strictly lower-right submatrices. Record the code, invocation, runtime environment, and exact outputs; separate exhaustive coverage of this finite universe from the general proof.
Deliverable 5: manuscript and seminar, 20 points. Write a 1,000–1,500-word educational manuscript containing an abstract, definitions, attributed lemma, complete proof, two counterexamples, experimental method and results, limitations, and references. Prepare a twelve-minute seminar outline. These are sections of your manuscript deliverable, not additional sections inserted into this chapter. Identify reproduction as the contribution and avoid unverified claims of priority.
Worked solution outline. The opening nonzero cells are $(1,3),(1,4),(2,3),(3,1),(3,2),(4,1)$, giving compression with ones at $(1,2),(2,1)$. For the general proof, write the pattern ones as $(i,\pi(i))$ and suppose they occur in distinct compressed rows $u_1\lt\cdots\lt u_k$ and columns $v_1\lt\cdots\lt v_k$. Lift one occupied cell from each block $(u_i,v_{\pi(i)})$. Ordered row intervals force the selected row coordinates to increase; ordered column intervals force their relative column ranks to be $\pi(i)$. These cells witness $P$ in $A$, contradicting avoidance. If an occurrence cannot fit in $B$, its avoidance is automatic.
For the reverse counterexample, place ones at $(1,1),(2,2)$ in a four-by-four zero matrix and merge rows and columns in pairs. The original contains $I_2$, but its compression has only one one. For the non-permutation counterexample, use $A=I_2$, merge its rows, leave its columns separate, and take $Q=(1\;1)$. The original avoids $Q$, but compression equals $Q$. For the order check, interchange the singleton row groups of the anti-diagonal two-by-two matrix; its reordered compression becomes $I_2$.
The finite audit should report 65,536 inputs, 1,008 avoiding matrices, histogram $1,16,84,216,309,252,110,20$ for weights zero through seven, and zero compression violations among avoiding inputs. Explain that diagonal capacity proves the independent extremal check of seven ones for four-by-four avoidance. The histogram is a computational result; the extremal bound and compression implication have general proofs.
Model abstract. “We give an explicit educational reproduction of the occupancy-compression lemma for permutation patterns, with ordered interval partitions and non-induced containment stated throughout. A witness-lifting proof establishes preservation of avoidance. Two small counterexamples explain the failure of the reverse implication and of a general binary-pattern extension. Exhaustive enumeration of four-by-four binary matrices verifies the $I_2$ specialization on all inputs and records 1,008 avoiding matrices with no compression violations. The computation audits a finite case; the proof establishes the general lemma.”
Validation and assessment. Award full proof credit only when both coordinate-order arguments and the role of the permutation condition are explicit. Award experiment credit only for a complete instance specification, matching outputs, and independent predicate agreement. Award writing credit for accurate attribution, a modest contribution statement, and a presentation that keeps hypotheses visible. Clear prose cannot compensate for an incorrect implication; correct counts cannot compensate for an omitted general proof.
Optional extension. Investigate which binary patterns admit a lifting theorem under additional within-block conditions. Start by requiring the selected ones of a pattern row to share a single original row, and similarly for pattern columns, then check whether the choices can be made consistently. This is a locally posed exploration, not a claim of a newly open problem. A successful extension must specify conditions, prove joint witness existence, and check the primary literature before asserting novelty.
Next in the Series
In Chapter 56: Research Seminars and Open-Problem Studios, we'll explore Choose a specialization and investigate a verified current problem.