Modern Graph Theory — Homework 13

Loading…

Modern Graph Theory — Homework 13

Assignments: June 9th, 2026

We first recall the form of Fisher's inequality used below.

Remark 1.

Maybe there is something wrong. It seems that what we need is Fisher's inequality ?

Theorem 1 (Fisher's inequality).

Let

\mathcal{A}=\{A_1,\ldots,A_m\} be a family of subsets of an N-element set. Suppose that, for some nonnegative integer \lambda,

|Ai\cap Aj|=\lambda\quad\text{for all }i\ne j,

\qquad

|A_i|>\lambda\quad\text{for all }i.

Then m\leq N. **Problem 1.** Apply Fisher's inequality to prove that n points in the plane either lie on one line or determine at least n distinct lines. **Proof.** Let P be the set of the given points, and let \mathcal{L} be the set of all lines determined by pairs of points in P. Suppose that the points are not all collinear. For each point x\in P, let

\mathcal{L}_x={\ell\in\mathcal{L}:x\in\ell}.

Every point lies on at least two lines in \mathcal{L}. Indeed, choose y\in P\setminus\{x\}. Since the points are not all on the line xy, there is a point z\in P outside xy, and the lines xy and xz are distinct. Therefore |\mathcal{L}_x|>1. For two distinct points x,y\in P, the only line belonging to both \mathcal{L}_x and \mathcal{L}_y is the line xy. Hence

|\mathcal{L}x\cap\mathcal{L}y|=1.

Applying Fisher's inequality to the family \{\mathcal{L}_x:x\in P\} on the ground set \mathcal{L}, with \lambda=1, gives

n=|P|\leq|\mathcal{L}|.

Thus the points determine at least n distinct lines. ∎ **Problem 2.** Let p be a prime and L\subseteq\mathbb{Z}_p. Suppose that \mathcal{F}\subseteq 2^{[n]} satisfies

|A|\notin L\pmod p\quad\text{for every }A\in\mathcal{F},

and

|A\cap B|\in L\pmod p

\quad\text{for every two distinct }A,B\in\mathcal{F}.

Prove that

|\mathcal{F}|\leq\sum_{k=0}^{|L|}\binom{n}{k}.

**Proof.** Put s=|L| and work over the field \mathbb{F}_p. For each A\in\mathcal{F}, define

fA(x1,\ldots,xn) =\prod{\ell\in L}\left(\sum{i\in A}xi-\ell\right).

Let \mathbf{1}_B\in\{0,1\}^n be the incidence vector of a set B. Then

fA(\mathbf{1}B) =\prod_{\ell\in L}(|A\cap B|-\ell).

If A\ne B, the assumption |A\cap B|\in L\pmod p gives f_A(\mathbf{1}_B)=0. On the other hand, since |A|\notin L\pmod p,

fA(\mathbf{1}A)\ne 0.

It follows that the functions f_A, restricted to the Boolean cube \{0,1\}^n, are linearly independent. To see this, suppose that

\sum{A\in\mathcal{F}}cAf_A=0

on \{0,1\}^n. Evaluating at \mathbf{1}_B leaves only the term c_Bf_B(\mathbf{1}_B), so c_B=0 for every B\in\mathcal{F}. Each f_A has degree at most s. On the Boolean cube, replacing every power x_i^r with r\geq1 by x_i does not change the function. Hence every f_A is represented by a multilinear polynomial of degree at most s. The space of such polynomials has basis

\left{\prod{i\in S}xi:S\subseteq[n],\ |S|\leq s\right}

and therefore has dimension

\sum_{k=0}^{s}\binom{n}{k}.

Since the functions \{f_A:A\in\mathcal{F}\} are linearly independent, the upper bound follows. ∎

PDF

Download the original write-up here.

Assignments: June 9th, 2026

We first recall the form of Fisher's inequality used below.

Remark 1.

Maybe there is something wrong. It seems that what we need is Fisher's inequality ?

Theorem 1 (Fisher's inequality).

Let

\mathcal{A}=\{A_1,\ldots,A_m\} be a family of subsets of an N-element set. Suppose that, for some nonnegative integer \lambda,

|Ai\cap Aj|=\lambda\quad\text{for all }i\ne j,

\qquad

|A_i|>\lambda\quad\text{for all }i.

Then m\leq N. **Problem 1.** Apply Fisher's inequality to prove that n points in the plane either lie on one line or determine at least n distinct lines. **Proof.** Let P be the set of the given points, and let \mathcal{L} be the set of all lines determined by pairs of points in P. Suppose that the points are not all collinear. For each point x\in P, let

\mathcal{L}_x={\ell\in\mathcal{L}:x\in\ell}.

Every point lies on at least two lines in \mathcal{L}. Indeed, choose y\in P\setminus\{x\}. Since the points are not all on the line xy, there is a point z\in P outside xy, and the lines xy and xz are distinct. Therefore |\mathcal{L}_x|>1. For two distinct points x,y\in P, the only line belonging to both \mathcal{L}_x and \mathcal{L}_y is the line xy. Hence

|\mathcal{L}x\cap\mathcal{L}y|=1.

Applying Fisher's inequality to the family \{\mathcal{L}_x:x\in P\} on the ground set \mathcal{L}, with \lambda=1, gives

n=|P|\leq|\mathcal{L}|.

Thus the points determine at least n distinct lines. ∎ **Problem 2.** Let p be a prime and L\subseteq\mathbb{Z}_p. Suppose that \mathcal{F}\subseteq 2^{[n]} satisfies

|A|\notin L\pmod p\quad\text{for every }A\in\mathcal{F},

and

|A\cap B|\in L\pmod p

\quad\text{for every two distinct }A,B\in\mathcal{F}.

Prove that

|\mathcal{F}|\leq\sum_{k=0}^{|L|}\binom{n}{k}.

**Proof.** Put s=|L| and work over the field \mathbb{F}_p. For each A\in\mathcal{F}, define

fA(x1,\ldots,xn) =\prod{\ell\in L}\left(\sum{i\in A}xi-\ell\right).

Let \mathbf{1}_B\in\{0,1\}^n be the incidence vector of a set B. Then

fA(\mathbf{1}B) =\prod_{\ell\in L}(|A\cap B|-\ell).

If A\ne B, the assumption |A\cap B|\in L\pmod p gives f_A(\mathbf{1}_B)=0. On the other hand, since |A|\notin L\pmod p,

fA(\mathbf{1}A)\ne 0.

It follows that the functions f_A, restricted to the Boolean cube \{0,1\}^n, are linearly independent. To see this, suppose that

\sum{A\in\mathcal{F}}cAf_A=0

on \{0,1\}^n. Evaluating at \mathbf{1}_B leaves only the term c_Bf_B(\mathbf{1}_B), so c_B=0 for every B\in\mathcal{F}. Each f_A has degree at most s. On the Boolean cube, replacing every power x_i^r with r\geq1 by x_i does not change the function. Hence every f_A is represented by a multilinear polynomial of degree at most s. The space of such polynomials has basis

\left{\prod{i\in S}xi:S\subseteq[n],\ |S|\leq s\right}

and therefore has dimension

\sum_{k=0}^{s}\binom{n}{k}.

Since the functions \{f_A:A\in\mathcal{F}\} are linearly independent, the upper bound follows. ∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 13

Search

Modern Graph Theory — Homework 13

Assignments: June 9th, 2026

PDF

Assignments: June 9th, 2026

PDF