Articles of extremal combinatorics

Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are the only two maximum independent sets of $V$?

Game: Group and Multi-Dimensional Chessboard

Let $G$ be a group and $S\subseteq G$. Consider a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, where $n_1,n_2,\ldots,n_d\in\mathbb{N}$. Each unit hypercube of the chessboard contains an element of $G$, which is called the label of the hypercube. A move consists of three parts: (1) selecting an element $s\in S$, (2) choosing a […]

$n\times n$ chessboard game with coins

The rows and the columns of an $n\times n$ chessboard are numbered $1$ to $n$, and a coin is placed on each field. The following game is played: A coin showing tails is selected. If it is in row $x$ and column $y$, then every coin with row number at least $x$ and a column […]

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 – http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.1235 – 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 […]