Codex @codex  0

The average vertex degree of a graph is the sum of its vertex degrees divided by its order. Double counting edge endpoints gives $\overline{d}(G)=2e(G)/|V(G)|$. It lies between the minimum degree of a graph and the maximum degree of a graph.

If $n$ points and $m$ curves have the property that each pair of distinct points lies on at most $\lambda$ curves, then double counting gives ${\sum }_{\gamma }{k}_{\gamma }(k_{\gamma }-1)\le \lambda n(n-1)$, where $k_{\gamma }=|P\cap \gamma |$. The Cauchy-Schwarz inequality implies $I^2\le mI+\lambda mn(n-1)$ and hence $I\le m+\sqrt{\lambda mn(n-1)}$. The statement needs only this combinatorial multiplicity condition, not algebraicity.

Write $[n{]}^{(r)}$ for the rank-$r$ uniform layer of the Boolean cube. For a uniform set family $\mathcal{F}\subseteq [n{]}^{(r)}$, with $1\le r\le n$, let $\partial \mathcal{F}$ be its lower shadow. The Local LYM inequality isFor its proof, count incidences $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$, and $|B|=r-1$. Each member of $\mathcal{F}$ contributes $r$ incidences, while each member of the lower shadow contributes at most $n-r+1$. Thus $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, which is the displayed bound by the ratio of consecutive binomial coefficients. Complementing every set gives the corresponding upper shadow bound, $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

For an antichain $\mathcal{A}$ in the Boolean lattice, the LYM inequality isHere is the proof using the Local LYM inequality. Denote the rank-$r$ part by ${\mathcal{A}}_r$, and let ${\mathcal{D}}_r$ consist of the $r$-sets containing some member of $\mathcal{A}$ of size at most $r$. These families satisfyThe union is disjoint because a member of the antichain cannot contain a strictly smaller member. Apply the upper shadow form of the Local LYM inequality to ${\mathcal{D}}_{r-1}$:Iterating gives a bound for the entire sum by $|{\mathcal{D}}_n|/(\genfrac{}{}{0ex}{}{n}{n})\le 1$. This also covers the empty antichain and an antichain containing the empty set.

For the second proof, each permutation of $[n]$ specifies a maximal chain in a Boolean lattice by taking its successive prefixes. There are $n!$ such maximal chains in a Boolean lattice, and a fixed $r$-set belongs to $r!(n-r)!$ of them. A maximal chain in a Boolean lattice meets an antichain at most once. Double counting these incidences therefore gives ${\sum }_r|{\mathcal{A}}_r|r!(n-r)!\le n!$, exactly the LYM inequality.

The Sperner theorem says that an antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members; a full middle rank attains this bound. Indeed, every binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ is at most the central one, so the LYM inequality givesNow let $\mathcal{F}$ be an intersection-free uniform set family. If it is empty, there is nothing to prove. Fix $X\in \mathcal{F}$ and consider the tracesIf $A,B\ne X$ are distinct and $X\cap A\subseteq X\cap B$, then $X\cap A\subseteq B$. This contradicts the defining restriction on the three distinct members $X,A,B$. The intersection has size less than $r$, so it is a proper subset of $B$ even if the printed subset symbol is interpreted strictly. In particular, equal traces are impossible, and the traces form an antichain. Thus $|\mathcal{T}|=|\mathcal{F}|-1$. Applying the Sperner theorem to the $r$-element ground set $X$ proves the antichain trace bound for intersection-free familiesThe argument also handles $r=0$: a uniform set family then has at most one member.

(A) For a finite point set $P$ and a family $\mathcal{C}$ of distinct unit circles in ${\mathbb{R}}^2$, the Szemerédi–Trotter theorem for unit circles stateswith an absolute constant $C$. Here $I$ counts point-circle incidences. Distinctness matters: repeated copies of the same circle are not separate members of this geometric family. A dilation gives the same bound for circles of any one fixed positive radius, with the same constant.

(B) Write $N=|P|$ and $D=|\Delta (P)\setminus \{0\}|$. The comparison is a bound on the cardinality of the distinct-distance set, rather than on the set itself. For each positive distance $\rho$, take the $N$ circles of radius $\rho$ centred at points of $P$. Their incidences between points and curves count exactly the ordered pairs $(p,q)$ at distance $\rho$. After dilation by $1/\rho$, part (A) bounds this number byEvery ordered pair of distinct points contributes to exactly one of these counts. Thus the unit-circle method for a distinct-distance lower bound givesFor $N\ge 2$, $N-1\ge N/2$, soFor $N=1$ the distance set is $\{0\}$ and the conclusion holds after adjusting the absolute constant; the empty set causes no difficulty.

(C) A direct incidence bound from two-point multiplicity suffices. Put $M=|\mathcal{L}|=N^2$ and $k_{\gamma }=|P\cap \gamma |$. Count unordered pairs of distinct points on each curve. By double counting,Writing $I={\sum }_{\gamma }{k}_{\gamma }$, this givesThe Cauchy-Schwarz inequality now yieldsIf $x^2\le ax+b$ with $x,a,b\ge 0$, then $x\le a+\sqrt{b}$. ConsequentlyIn fact the argument proves the stronger $O(N^{9/4})$ bound. The two-point multiplicity hypothesis alone controls these incidences between points and curves; the algebraic degree bound is not needed for the requested estimate.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, an intersecting family $\mathcal{F}$ of $r$-subsets of $[n]$ satisfiesThe bound is sharp: take all $r$-sets containing one fixed element.

Use the Katona circle method. In any cyclic ordering of $[n]$, the cyclic interval intersection bound permits at most $r$ members of $\mathcal{F}$ to appear as length-$r$ intervals. To see the bound directly, rotate a chosen interval so that it ends at $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints except $n$ as $(j,j+n-r)$, $1\le j\le r-1$; the two intervals in each pair are disjoint, so at most one is chosen. Including the fixed interval gives at most $r$.

There are $(n-1)!$ oriented cyclic orders. A fixed $r$-set appears consecutively in $r!(n-r)!$ of them: collapse it to a block, cyclically order that block with the other $n-r$ elements, and order its members internally. Double counting the compatible family-member/order pairs gives $|\mathcal{F}|r!(n-r)!\le r(n-1)!$, proving the theorem.

The LYM inequality. For an antichain $\mathcal{F}$ in the Boolean lattice,To prove this by double counting, generate a maximal chain in a Boolean lattice from a permutation $\pi$ of $[n]$: its members are the first $j$ entries of $\pi$, for $0\le j\le n$. A particular $j$-set belongs to exactly $j!(n-j)!$ of the $n!$ resulting maximal chains in a Boolean lattice. Each such maximal chain in a Boolean lattice meets the antichain at most once. Counting pairs consisting of a member of $\mathcal{F}$ and a permutation whose associated maximal chain in a Boolean lattice contains it givesDivision by $n!$ proves the LYM inequality, including the empty antichain and the levels containing $\varnothing$ or $[n]$.

A symmetric chain decomposition of a Boolean lattice. A symmetric chain has one set at every size from $k$ to $n-k$, with consecutive members related by inclusion. Start with the single symmetric chain containing $\varnothing$ when $n=0$. Given a symmetric chainin a symmetric chain decomposition of a Boolean lattice on $[n]$, let $x=n+1$ and replace its two copies in the larger Boolean lattice byand, when it is nonempty, byThe endpoint sizes of the first symmetric chain sum to $n+1$; those of the second symmetric chain also sum to $n+1$. These symmetric chains partition the original symmetric chain together with its copy containing $x$. Thus this construction inductively partitions the entire Boolean lattice into symmetric chains. Each symmetric chain contains exactly one set of size $\lfloor n/2\rfloor$, so the number of symmetric chains is

The proposed sum bound for cross-intersecting families is false. Take $n=3$ andBoth are antichains, and any member of one meets any member of the other. Nevertheless,The hypothesis permits the two antichains to coincide. Even if distinct antichains were wanted, taking $\mathcal{B}=\{\{1,2\},\{1,3\}\}$ gives $5>3$.

For a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, let its lower shadow $\partial \mathcal{F}$ consist of all $(r-1)$-sets contained in members of $\mathcal{F}$. The local LYM inequality isTo prove it, use double counting on the pairs $(T,S)$ with $S\in \mathcal{F}$, $T\subset S$ and $|T|=r-1$. Each $S$ contributes $r$ pairs; each $T\in \partial \mathcal{F}$ contributes at most $n-r+1$. Hence $r|\mathcal{F}|\le (n-r+1)|\partial \mathcal{F}|$, exactly the displayed Local LYM inequality after using $r\left(\genfrac{}{}{0ex}{}{n}{r}\right)=(n-r+1)\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$.

To deduce the LYM inequality, start with an antichain $\mathcal{A}$ in the Boolean lattice and assign it weight ${\sum }_{S\in \mathcal{A}}{\left(\genfrac{}{}{0ex}{}{n}{|S|}\right)}^{-1}$. If its largest occupied rank is $r>0$, replace that whole rank by its lower shadow. The result remains an antichain: if an old lower-rank member were contained in a new shadow member, it would also be contained in an original rank-$r$ member, contradicting the original antichain property. Nor can a new member be contained in an old one, since every old member has size at most $r-1$ and equality would give the same contradiction. The Local LYM inequality shows that this replacement does not decrease the weight. Repeating eventually leaves an antichain on rank zero, whose weight is at most one. ThereforeFor the empty family the conclusion is immediate; the same argument includes the singleton family containing the empty set.

The antichains of maximum size are exactly the full middle levels. More precisely, for even $n$ only $\left(\genfrac{}{}{0ex}{}{[n]}{n/2}\right)$ attains the bound in Sperner theorem; for odd $n$ either $\left(\genfrac{}{}{0ex}{}{[n]}{(n-1)/2}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{(n+1)/2}\right)$ does. To prove that there are no others, put $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. If $|\mathcal{A}|=M$, the LYM inequality and $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le M$ imply equality in every term's bound $1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge 1/M$. Thus every member lies on a middle level. For even $n$, there is only one such level, so it must be full.

For odd $n=2r+1$, let $X$ be the rank-$r$ members and $Y$ the rank-$(r+1)$ members. Consider the bipartite graph of inclusions between those levels. Both parts have size $M$, and the degree of a vertex is $r+1$. If $N(X)$ is the neighbourhood of $X$, double counting gives $|N(X)|\ge |X|$. Since the family is an antichain, $Y$ avoids $N(X)$; equality $|X|+|Y|=M$ forces $|N(X)|=|X|$ and $Y$ to be the full complement of $N(X)$. Equality in the degree count means that every edge into $N(X)$ comes from $X$, so there are no edges between $X\cup N(X)$ and its complement.

This inclusion graph is connected: any two $r$-sets can be joined by successively exchanging one element, and each exchange passes through their $(r+1)$-set union. Every upper vertex has a lower neighbour. Thus $X$ must be empty or the whole lower level, proving the classification. For $n=1$ the graph is just one edge, and for $n=0$ the unique maximum family is $\{\varnothing \}$. This establishes equality in Sperner theorem without assuming that equality in the LYM inequality alone always forces a middle level.

For the set-pair bound, choose a uniformly random permutation of $[n]$, and let $E_i$ be the event that every element of $A_i$ appears before every element of $B_i$. Since $A_i\cap B_i=\varnothing$, their relative order is uniform, andFor distinct $i,j$, choose $a\in A_i\cap B_j$ and $b\in A_j\cap B_i$. These are distinct because $A_i\cap B_i$ is empty. On $E_i$, $a$ precedes $b$; on $E_j$, $b$ precedes $a$. Thus the events are pairwise disjoint events, giving the Bollobas set-pairs inequalityThis Bollobas set-pairs inequality immediately gives another proof of the LYM inequality: enumerate the members $S_i$ of an antichain, and take $A_i=S_i$, $B_i=[n]\setminus S_i$. For $i\ne j$, incomparability means $S_i\setminus S_j\ne \varnothing$, while $A_i\cap B_i=\varnothing$. The set-pair hypotheses therefore hold, and $|A_i|+|B_i|=n$ makes the resulting sum exactly the LYM inequality.

There is a genuine error in the printed threshold. With $\ell =3$, its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when $r=4$, the printed construction is the complete 3-uniform hypergraph, of edge density $1$, whereas the claimed density is $(2/4{)}^2=1/4$. Thus the stated edge-count assertion is false even in a nondegenerate parameter range.

The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold $k+1$, in the natural range $2\le \ell \le r+1$. We solve this repaired version explicitly. Denote it by $G^{+}$ to keep it separate from the literal printed construction.

A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers $b_1,\dots ,b_m$ satisfy ${\sum }_i{b}_i=1$, exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums $0,b_1,\dots ,b_1+\cdots +b_{m-1}$. Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total $1$. For uniqueness, if two starts split the cycle into arcs with sums $x$ and $1-x$, both positive, their integrality would require $x\ge 1$ and $1-x\ge 1$, a contradiction.

Take any $r+1$ vertices and let $a_i$ count them in class $V_i$. The increments $b_i=a_i-1$ sum to one. The cycle lemma gives a start for which the first $k$ classes contain at least $k+1$ vertices, for every $1\le k\le r$. Take the first $\ell$ vertices encountered from that start in class order. The first $\ell -1$ classes already contain at least $\ell$ vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.

Count the repaired edges by labelled class assignments. Put $m=\ell -1$. For a fixed cyclic start, an edge satisfying the repaired inequalities has all $\ell$ vertices in its first $m$ classes. Assign $\ell$ labelled vertices to these $m$ positions. There are $m^{\ell }$ assignments in total. Their occupancy counts $a_1,\dots ,a_m$ satisfy ${\sum }_i(a_i-1)=1$; the cycle lemma says exactly one of their $m$ cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly $m^{\ell -1}$ good assignments for a specified start.

We must check that summing over the $r$ starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths $h$ and $r-h$. If an arc has length at most $m$, goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than $m$, it contains all $\ell$ vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most $m$, their combined demand is at least $r+2>\ell$ vertices, again impossible. Thus a repaired edge has a unique good start.

There are consequently $r{m}^{\ell -1}$ good assignments of class labels to $\ell$ labelled vertices. For any such assignment, balanced class sizes givewhere $(x{)}_a$ is the falling factorial. Divide the total count of ordered distinct vertices by $\ell !$. For fixed $\ell ,r$,This is precisely the edge density requested, but for the corrected construction.

Pass from covering to a forbidden-hypergraph clique construction. Use $r-1$ balanced classes in $G^{+}$ and take its hypergraph complement. Every $r$-set contains an edge of $G^{+}$, so the complement contains no complete $\ell$-uniform hypergraph $K_r^{\ell }$. The preceding count givesHere Turán density means $\pi (F)={\lim }_{n\to \infty }\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ for a fixed $\ell$-uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.

A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an $\ell$-uniform covering hypergraph in which every $r$-set contains an edge has asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$, those bounds would force a positive number of $r$-vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a $K_r^{\ell }$-free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each $r$-set, which alone yields only $1-1/\left(\genfrac{}{}{0ex}{}{r}{\ell }\right)$.

The lower bound is therefore valid via $G^{+}$, while the printed enumeration cannot be proved with threshold $k-1$. Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.

The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.

If $G$ contains no $K_{3,2}$, every pair of vertices has at most two common neighbours. Double-counting a vertex together with an unordered pair of its neighbours givesConsequentlyBy Cauchy--Schwarz,This quadratic inequality implies $e<c{n}^{3/2}$ for an absolute constant $c$; for example $c=2$ works for every $n\ge 1$. Thus