Articles of extremal combinatorics

maximum size of a $k$-intersecting antichain of $$

What is the maximum size of an antichain of $[n]:=\{1,2,3,\dots,n\}$ (say $\mathcal{A}$) such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? By antichain, I mean an antichain of the poset $(2^{[n]},\subseteq)$ where $2^{[n]}$ is the power set of $[n]$. Related: 833011

minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these lines conicide. How can we arrange the points such as the total number of lines is minimized? I started with solving the dual […]

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4×3 and 5×4 rectangles, What is the minimum square partition of an almost-square rectangle?. Let: An almost-square-rectangle be a rectangle that has a width $w$ and height $h=w-1$. […]

The sum of a polynomial over a boolean affine subcube

Let $P:\mathbb{Z}_2^n\to\mathbb{Z}_2$ be a polynomial of degree $k$ over the boolean cube. An affine subcube inside $\mathbb{Z}_2^n$ is defined by a basis of $k+1$ linearly independent vectors and an offset in $\mathbb{Z}_2^n$. [See “Testing Low-Degree Polynomials over GF(2)” by Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron – – for more details] […]

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it’s indeterminable with minimal information: A graph has 17 vertices and 129 edges. Hamiltonian graphs are proved by, as long as the vertices are greater than or equal to 3 (which this is), then if the sum of […]

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I want to know is: What is the size of the group of mixtures such that no mixture in the […]

Tricky (extremal?) combinatorics problem

Apologies for being unsure the best way to express this problem. I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit together again. What’s the maximum possible number of re-seatings? Generally, given a set S of students partitioned into […]

chromatic number of a graph versus its complement

What can be said about the rate of growth of $f(n)$, defined by $$f(n) = \min_{|V(G)|=n} \left[ \chi(G) + \chi(\bar{G}) \right],$$ where the minimum is taken over all graphs $G$ on $n$ vertices. Two observations. (1) Either $G$ or $\bar{G}$ contains a clique on roughly $\log{n}$ vertices by Ramsey theory, so $f(n) \ge c_1 \log […]

Bounds on the size of these intersecting set families

Are there good lower bounds on the size of a collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common?

Graph with 10 nodes and 26 edges must have at least 5 triangles

This is not a homework question, but I would appreciate if people would treat this as if it were homework. I am looking for (nonspoiler) hints. I would like to prove that given any graph with 10 nodes and 26 edges, there must be at least 5 triangles. Here is the progress I made so […]