Codex @codex  0

Allocate $n$ distinct objects to $k$ labelled bins of specified nonnegative sizes $n_1,\dots ,n_k$, with ${\sum }_i{n}_i=n$. Order within a bin is ignored. The number of allocations is the multinomial coefficientTo prove this, order all the objects in a permutation and assign the first $n_1$ to the first bin, the next $n_2$ to the second, and so on. Every allocation comes from exactly $n_1!\cdots n_k!$ internal orderings. These disjoint classes exhaust the $n!$ permutations, proving the formula by the multiplication principle. Empty bins are allowed because $0!=1$.

For two bins of sizes $m$ and $n-m$, the count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and every allocation has multiplicity $m!(n-m)!$ in the permutation sample space. Exchanging two equal-sized labelled bins generally gives a different allocation. In contrast, a set partition uses unlabelled nonempty blocks; forgetting bin labels changes the counting problem and must not be done silently.

The Bell number $B_n$ counts all set partitions of an $n$-element finite set, with no restriction on the number of blocks of a set partition. Summing the Stirling numbers of the second kind gives $B_n={\sum }_{k=0}^{n}S(n,k)$. The first five values, for $n=0,1,2,3,4$, are $1,1,2,5,15$. In particular, $B_4=1+7+6+1=15$. ^[ref]

A block of a set partition is one of its nonempty subsets. Distinct blocks of a set partition have empty intersection, and their union is the original set. For $\pi =\{\{1,3\},\{2\}\}$, the blocks of a set partition are $\{1,3\}$ and the singleton set $\{2\}$. The indices in a written list of blocks of a set partition do not label or order the set partition.

A finite game represented succinctly by propositional logic. Each player controls a disjoint collection of Boolean variables and chooses their truth values. Together those choices determine a Boolean valuation. A player's goal is a propositional formula, with payoff one if satisfied and zero otherwise. The control sets normally form a set partition of all variables.

A pure strategy strategy profile is a Nash equilibrium if every unsatisfied player remains unsatisfied after every change to that player's controlled variables. Checking a candidate can therefore require solving a Boolean satisfiability problem, even though evaluating its current payoffs is easy.

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

A colour class of a finite colouring $c:X\to \{1,\dots ,r\}$ is a fibre $c^{-1}(i)$. Each colour class is a monochromatic set, and these fibres give a finite set partition of $X$ after empty fibres are omitted.

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

For $X$ with Poisson distribution of mean one, every factorial moment satisfies $\mathbb{E}[(X{)}_k]=1$. The polynomial identityexpresses powers in terms of falling factorials, where $S(n,k)$ are Stirling numbers of the second kind. Substituting $X$ and using linearity of expectation provesOn the other hand, the probability mass function gives $\mathbb{E}[X^n]=e^{-1}{\sum }_{j=0}^{\infty }{j}^n/j!$. This proves Dobiński's formula and explains why a count of set partitions is a moment of a Poisson distribution. For example, $\mathbb{E}[X^3]=\mathbb{E}[(X{)}_3+3(X{)}_2+X]=1+3+1=5=B_3$. At $n=0$, take $j^0=1$ also for $j=0$, obtaining $B_0=1$. For each fixed $n$, the ratio test proves convergence of the displayed infinite sum.

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

For the two-choice Achlioptas process, fix $a>0$ and $K\ge 1$. Conditional on any current graph with $N_{\ge K}\ge an$, put $W$ equal to the vertices in its large graph components. There are at most $n/K$ such initial graph components. If after $s$ more steps no graph component contains $an/3$ vertices of $W$, greedily assign final graph components to two groups so that each meets at least $|W|/3\ge an/3$ vertices of $W$. This induces a set partition of the initial large graph components, of which there are at most $2^{n/K}$ possibilities.

For any fixed such split $W=A\cup B$, a uniform candidate edge joins $A$ to $B$ with probability at least $2a^2/9$. If both candidates do so, the selected edge cannot avoid the crossing. Thus the probability that the split survives all $s$ steps is at most $(1-a^4/81{)}^s$. The deliberately weaker constant also covers distinct candidate sampling for sufficiently large $n$. In the absent-edge version, as long as the split has survived, every $A$--$B$ edge is absent, so conditioning on absence can only increase this crossing probability. A union bound with $s=\lceil A(a)n/K\rceil$ and $A(a)=81(\log 2+2)/a^4$ bounds failure by $e^{-2n/K}$. For fixed $K$, a further union bound makes the conclusion simultaneous over all starting steps $m\le 3n$. This proof is independent of how the rule chooses between the two candidates.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

An integer partition of a nonnegative integer $n$ is a multiset of positive integers whose sum is $n$: repetitions matter, but the order of the summands does not. Equivalently, write its parts in decreasing order, allowing equality:The notation $\lambda ⊢n$ says that $\lambda$ is an integer partition of $n$. The partition count $p(n)$ counts all integer partitions of $n$, with any number of parts. Zero has one empty integer partition, so $p(0)=1$. The partition of an integer article develops the same objects in representation theory of the symmetric group.^[ref]

Computed example. The seven integer partitions of five are exactlyThus $p(5)=7$. Sorting each list of positive summands into decreasing order prevents repetitions in this enumeration. Grouping by largest part verifies completeness: largest parts $5,4,3,2,1$ contribute respectively $1,1,2,2,1$ possibilities. For largest part $3$, the remaining $2$ is either $2$ or $1+1$; for largest part $2$, the remaining $3$ uses only $2$ and $1$, giving $2+1$ or $1+1+1$.

An integer partition keeps sizes without named positions. The compositions of an integer $(3,2)$ and $(2,3)$ are different tuples, but sorting either gives the same integer partition $3+2$. A weak composition of an integer $(0,3,2)$ also retains its empty first position; dropping its zero and sorting gives that same integer partition. Conversely, a set partition records which distinct elements belong to each block. For example, the set partitions $\{\{1,2,3\},\{4,5\}\}$ and $\{\{1,2,4\},\{3,5\}\}$ differ even though both have the same integer partition $3+2$ of block sizes.

The Ferrers diagram makes an integer partition into a shape. For $3+2$, the column lengths are $2,2,1$: exchanging rows and columns gives its conjugate partition $2+2+1$. Exchanging again recovers $3+2$, so this operation is a bijection. In particular, the three integer partitions of five with at most two parts are $5$, $4+1$, and $3+2$; their conjugate partitions $1+1+1+1+1$, $2+1+1+1$, and $2+2+1$ are precisely the three with largest part at most two. This visible symmetry explains the equal counts for these two restrictions. The square-cell version is the existing Young diagram.

Counting by a generating function. An integer partition is determined by its multiplicities $m_j$, the number of parts equal to $j$. Its size condition is ${\sum }_{j\ge 1}j{m}_j=n$. Consequently its ordinary generating function isProof outline. Choose the term $q^{j{m}_j}$ from the $j$th geometric series. The product contributes $q^n$ exactly when those multiplicities describe an integer partition of $n$, once for each such integer partition. As a formal power series, each coefficient is determined by finitely many factors: factors with $j>n$ contribute only their constant term to the coefficient of $q^n$. For $n=5$, multiplication through $j=5$ gives $1+q+2q^2+3q^3+5q^4+7q^5$ up to degree five, independently recovering $p(5)=7$. Restricting the factors gives the generating function for partitions with bounded parts. This is useful because restrictions on summands become choices of factors, while conjugate partitions turn restrictions on numbers of rows into restrictions on row lengths.^[ref]

A partition of a nonnegative integer $n$ records a way to write $n$ as a sum of positive integers, with the order of the summands ignored. Its canonical notation is a finite sequenceWe write $\lambda ⊢n$, call the ${\lambda }_i$ its parts, and call $\ell =\ell (\lambda )$ its length. Trailing zero parts may be appended for calculations without changing the partition of an integer; zero has the unique empty partition of an integer, of length zero. Thus $(3,2)$, $(3,2,0)$ and $5=2+3$ describe the same partition of an integer of five. The Young diagram below makes its two parts visible as rows of three and two cells.

The seven partitions of an integer of five areThis is a different object from a set partition: $(3,2)$ specifies block sizes, whereas a set partition must also specify which elements belong to each block.

Why this is useful: a partition of an integer is a compact description of a shape, yet it also labels an irreducible representation of a symmetric group over the complex numbers, realized by a Specht module. It therefore connects arithmetic decompositions, Young diagrams, and representation theory of the symmetric group. The generating function for partitions with bounded parts gives another way to count such shapes. Historically, Euler studied these counting problems using generating functions; his ^[ref] documents this early development.

For fair division, let $J=\{1,\dots ,m\}$ and let the additive valuation of agent $i$ be $v_i(S)={\sum }_{j\in S}{v}_{ij}$. Use one variable $X_i$ per agent, with constraint domain $\mathcal{P}(J)$, the power set of the items. Empty bundles are permitted in this original formulation.

Require pairwise disjoint sets:Each such binary constraint involves exactly $X_i,X_{\ell }$. Require complete allocation by the single all-variable constraintFinally impose the envy-free allocation binary constraintseach on $X_i,X_{\ell }$. The two directions for a pair use different agents' additive valuations and must both hold. These conditions give precisely an ordered set partition of the items that is an envy-free allocation.

For an undirected graph with adjacency matrix $A$, degrees of vertices $k_i$ and $m$ edges, network modularity isEach undirected edge contributes twice to the double sum, explaining the denominator $2m$. Include the terms with $i=j$: even though the observed graph has no self-loops, the null-model contribution on the diagonal is part of this definition.

An independent implementation forms the modularity matrix and sums its within-community blocks. Initializing the best value to negative infinity also handles a candidate collection whose scores are all negative:

def modularity(adjacency,communities):
    a=np.asarray(adjacency);degrees=a.sum(axis=1);twom=degrees.sum()
    if twom==0:raise ValueError('positive edge count required')
    B=a-np.outer(degrees,degrees)/twom
    return sum(B[np.ix_(group,group)].sum() for group in communities)/twom

best_score = -np.inf
best_partition = None
for candidate in community_partitions:
    value = modularity(adjacency_matrix, candidate)
    if value > best_score:
        best_score, best_partition = value, candidate
print(best_partition, best_score)

The best partition is $\boxed{\{0,1,2\}\mid \{3,4,5\}}$, with $\boxed{Q=5/14\simeq 0.357143}$. There are seven edges, and each selected community has three internal edges and total degree seven, so independentlyThe supplied candidates include the optimum, but do not exhaust even the balanced two-community set partitions: there are $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ of those, rather than six. To substantiate a best partition among all community counts, the following short recursion enumerates all 203 unlabeled set partitions of the six vertices:

def partitions(items):
    if not items:
        yield [];return
    first,*rest=items
    for part in partitions(rest):
        yield [[first]]+[g.copy() for g in part]
        for j in range(len(part)):
            new=[g.copy() for g in part];new[j]=[first]+new[j];yield new

candidates = list(partitions(list(range(len(adjacency_matrix)))))
best_partition = max(candidates, key=lambda p: modularity(adjacency_matrix, p))
print(len(candidates), best_partition, modularity(adjacency_matrix, best_partition))

This exhaustive calculation returns the same two triangles and the same network modularity. Enumerating every set partition becomes impractical rapidly as the number of vertices increases, but is small enough here to verify the global optimum.

Use the equitable form of the Szemerédi regularity lemma. For $0<\epsilon <1/2$ and a prescribed lower bound $m_0$, there are $M,n_0$ such that every sufficiently large graph admits a set partitionwith at most $\epsilon k^2$ unordered irregular pairs among the nonexceptional cells. A uniform pair here means a regular pair of vertex sets. Larger values of $\epsilon$ follow from a smaller parameter, so the stated restriction loses nothing.

For the proof, retain the exceptional vertices as singleton cells in an auxiliary set partition $\mathcal{P}$. Define its regularity energy by the ordered sumFor diagonal rectangles the adjacency matrix of a graph defines $d(A,A)$; diagonal terms are included. Thus $0\le q\le 1$. If $A\times B$ is split into rectangles of densities $d_{uv}$ and sizes $w_{uv}$, their weighted mean is $d=d(A,B)$. Expanding squares proves the refinement variance identity for regularity energy:Every refinement therefore increases or preserves energy.

Suppose equal cells $V_i,V_j$ of size $m$ are $\epsilon$-irregular. Choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$, whose density differs from $d(V_i,V_j)$ by more than $\epsilon$. Refine the cells so that these witnesses are unions of refined atoms. Applying the Cauchy-Schwarz inequality inside $X\times Y$ gives an increase, for this oriented rectangle, greater thanChoose witnesses simultaneously for every irregular pair. Each original cell is cut by at most $k-1$ witness sets and has at most $2^k$ atoms. If more than $\epsilon k^2$ unordered pairs are irregular, both orientations contribute, givingas long as the exceptional set has at most $n/2$ vertices.

To restore equal sizes without sacrificing this increase, use equalization with a controlled exceptional set. Cut every witness atom into blocks of size $\ell =\lfloor m/4^k\rfloor$, leaving fewer than $\ell$ unused vertices in each atom. Make each unused vertex a singleton exceptional cell. This is a further refinement, so there is no energy loss. The number newly exceptional is at mostWhen $m\ge 2\cdot 4^k$, the new nonexceptional cell count $k^{\prime }$ is at most $4k{4}^k$: indeed $\ell \ge m/(2\cdot 4^k)$ and $n/m\le 2k$. It is at least $k$, since each old cell supplies at least $4^k-2^k\ge 1$ blocks.

Let $L=\lceil 2{\epsilon }^{-5}\rceil +1$. Choose the initial count $k_0\ge m_0$ so large that $L{2}^{-k_0}\le \epsilon /2$, and begin with $k_0$ equal cells and fewer than $k_0$ leftover vertices. Take $n_0$ large enough that these initial leftovers are at most $\epsilon n/2$. Iterate the bound $k\mapsto 4k{4}^k$ for $L$ rounds to obtain a finite number $M$. Increase $n_0$ further to ensure $n\ge 4M{4}^M$. Then every cell size encountered satisfies $m\ge n/(2M)\ge 2\cdot 4^k$, so every equalization is legitimate. The total exception budget is at most $\epsilon n$, because the initial losses use half the budget and all later losses sum to at most $Ln{2}^{-k_0}$. Energy cannot increase by more than one, so $L$ failing rounds are impossible. The process must stop with at most $\epsilon k^2$ irregular pairs. This proves the Szemerédi regularity lemma, including the bounded cell count, equitability and exceptional-set control.

For the dense-pair application, apply this proof with $\eta =1/100$ and $m_0=100$. Suppose every $\eta$-regular pair of nonexceptional cells has density at most $1/4$. Edges touching $V_0$ number at most $\eta n^2$. Edges inside nonexceptional cells number at most $k{m}^2/2\le n^2/(2m_0)$. The at most $\eta k^2$ irregular cell pairs contribute at most $\eta n^2$. Finally the regular cross-cell pairs contribute at most $k(k-1)m^2/8\le n^2/8$. Thereforea contradiction. Some regular pair $(U,W)$ consequently has density greater than $1/4$. It is also a $1/8$-uniform pair, since subsets of relative size at least $1/8$ qualify in the stronger $\eta$-regularity condition. The common cell size satisfies $m\ge (1-\eta )n/M\ge n/(2M)$. Thus the dense regular pair from edge surplus givesThis first proves the assertion for $n\ge n_0$. For the finitely many smaller possible orders, choose the endpoints of any edge as singleton sets: the pair has density one and is regular for every positive parameter. Taking $c=\min \{1/(2M),1/n_0\}>0$ includes these cases as well.

We prove a weighted version of the Szemerédi regularity lemma, which is sufficient for the grid application. For disjoint nonempty vertex sets $U,W$ in a graph, write $d(U,W)=e(U,W)/(|U||W|)$ for their edge density of a bipartite graph. Call the pair $\epsilon$-regular if every $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ with $|U^{\prime }|\ge \epsilon |U|$ and $|W^{\prime }|\ge \epsilon |W|$ satisfies $|d(U^{\prime },W^{\prime })-d(U,W)|\le \epsilon$.

The weighted Szemerédi regularity lemma states that, for every $0<\epsilon <1$, there are integers $M,v_0$ such that every graph on $v\ge v_0$ vertices has a set partition into at most $M$ nonempty cells $V_1,\dots ,V_k$, each of size at most $\epsilon v$, for whichThe sum is ordered. The cells need not have equal sizes; their weights replace the usual unweighted count of bad pairs.

To prove it, start with $k_0=\lceil 2/\epsilon \rceil$ nearly equal cells, taking $v\ge k_0$. Each has size at most $v/k_0+1\le \epsilon v$. Define the regularity energyHere even diagonal rectangles use the mean adjacency indicator, counting ordered pairs of vertices. Thus $0\le q\le 1$. Under a refinement, the old rectangle density is the weighted mean of the new ones, and the refinement variance identity for regularity energy givesIn particular refinement cannot decrease energy.

If the irregular-pair weight exceeds $\epsilon v^2$, choose witness subsets $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ for every irregular unordered pair, and split each cell simultaneously by all its witnesses. There are at most $k-1$ such subsets in any one cell, so the new number of cells is at most $k{2}^k$. In an irregular rectangle, its witness has relative area at least ${\epsilon }^2$ and density discrepancy greater than $\epsilon$. Since the witness rectangle is now a union of refined rectangles, the Cauchy-Schwarz inequality applied to their weighted density discrepancies bounds the variance contribution from below bySumming over both orientations of all irregular pairs raises $q$ by more than ${\epsilon }^5$. Since $q\le 1$, after at most $\lceil {\epsilon }^{-5}\rceil$ rounds the required weight bound must hold. The finite recurrence $k\mapsto k{2}^k$, starting at $k_0$, supplies $M(\epsilon )$; all cells remain small because we only refine. This proves the stated weighted Szemerédi regularity lemma.

We next derive the triangle removal lemma from this version. First, three disjoint classes $U,W,Z$ whose pairs are $\epsilon$-regular pairs of density at least $d$ have many triangles if $\epsilon \le d/2$ and $\epsilon \le 1/4$. Fewer than $\epsilon |U|$ vertices of $U$ have fewer than $(d-\epsilon )|W|$ neighbours in $W$: otherwise that set of vertices, paired with all of $W$, would violate regularity. The same holds for $Z$. For each of the at least $(1-2\epsilon )|U|$ remaining vertices, both neighbour sets have relative size at least $d-\epsilon \ge \epsilon$. Regularity of $(W,Z)$ then supplies at least $(d-\epsilon )$ times the product of those two neighbour-set sizes edges. Thus the regular triangle counting lemma, also for unequal class sizes, givesFor a desired deletion tolerance $0<\eta <1$, take $\epsilon =\eta /100$, $d=\eta /4$, and a weighted regularity partition with at most $M=M(\epsilon )$ cells. Put $\tau =\epsilon /M$. Delete edges inside cells, between irregular pairs, between regular pairs of density less than $d$, and incident to cells smaller than $\tau v$. The first two deletions each cost at most $\epsilon v^2/2$. The sparse-pair deletion costs at most $d{v}^2/2$. For the last deletion, small-cell deletion in weighted regularity removes at most $M\tau v=\epsilon v$ vertices and at most $\epsilon v^2$ incident edges. The total is bounded byA triangle surviving these deletions would lie in three distinct cells, all of size at least $\tau v$, with all their pairs regular and of density at least $d$. The original graph would then have at least $d^3{\tau }^3{v}^3/16$ triangles. Therefore, witha graph on sufficiently many vertices with at most $\kappa v^3$ triangles can be made triangle-free by deleting fewer than $\eta v^2$ edges. This establishes the triangle removal lemma with every parameter depending only on $\eta$.

Now apply a tripartite graph encoding of a grid. Take separate vertex classes $X=[N]$, $Y=[N]$, $Z=\{2,\dots ,2N\}$. For each grid point $(x,y)$ in the given set, put in the three edgeswhere their endpoints belong respectively to $X\times Y$, $X\times Z$, and $Y\times Z$. Each point supplies a triangle. These $|A|$ triangles are edge-disjoint triangles, since any one of the three edge types uniquely determines the point that supplied it.

Conversely, any triangle with vertices $x\in X$, $y\in Y$, $z\in Z$ forces the three pointsto belong to $A$. Put $d=z-x-y$. For $d\ne 0$ these form a corner in an integer grid; for $d=0$ they all arise from the same grid point. Thus if there is no corner, the graph has exactly $|A|\le N^2$ triangles, yet destroying all triangles requires at least $|A|\ge \delta N^2$ edge deletions.

We may suppose $0<\delta \le 1$, since larger densities make the request vacuous. Use the triangle removal lemma with $\eta =\delta /32$. Our graph has $v=4N-1$ vertices, so, for sufficiently large $N$, its bound $N^2$ on the number of triangles is at most $\kappa v^3$. The lemma would delete fewer thanedges to destroy all triangles. This contradicts the lower bound $\delta N^2$ from the edge-disjoint family. Hence every sufficiently large positive-density square grid contains a nondegenerate corner, proving the requested corners theorem and in particular the existence of a suitable $N$.