Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10 votes
1 answer
374 views

How many positions of a tiling polygon can occur simultaneousy?

Let $T$ be a polygon which tiles the plane. For an instance of $T$ (mirrored or not), call the set of its translates a position of $T$. My question: How many different positions can occur in ...
Wolfgang's user avatar
  • 13.2k
3 votes
0 answers
183 views

Matrices with only two different entries and maximal determinant

Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$. I am interested in how big the determinant of such a matrix can be. For this, we define in a ...
Wolfgang's user avatar
  • 13.2k
0 votes
0 answers
110 views

Simpler lower bound for couples of disjoint sets

This is similar to a previous question, but simpler, I suppose. Let $\mathcal{B}$ be the family of all subsets of $[n]=\{1,2,\ldots,n\} $ of size $2$. Let $\mathcal{F} = \{\mathcal{A}_1,\ldots,\...
Fabius Wiesner's user avatar
55 votes
1 answer
3k views

Intersecting family of triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
Gil Kalai's user avatar
  • 24.2k
26 votes
2 answers
2k views

What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such ...
domotorp's user avatar
  • 18.3k
26 votes
3 answers
867 views

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple ...
a3nm's user avatar
  • 431
14 votes
1 answer
616 views

Minimal "sumset basis" in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$. I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...
pointer's user avatar
  • 197
11 votes
2 answers
772 views

Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line? Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0,...
Anurag's user avatar
  • 1,157
8 votes
0 answers
1k views

The state of art of the sunflower lemma

I am interesting in the sunflower system and its applications in computer science. Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...
WangYao's user avatar
  • 393
6 votes
2 answers
780 views

Conjecture about partitions of the powerset without the empty set

I would like to have some ideas about possibilities of proving or disproving the following conjecture: For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without ...
Fabius Wiesner's user avatar
5 votes
2 answers
433 views

Minimum number of transpositions to make two multiset permutations equal

I think this problem should have a known solution, but I wasn't able to find any reference. Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$. ...
Fabius Wiesner's user avatar
5 votes
0 answers
234 views

A combinatorial problem

What is the largest $m\times m$ $0/1$ matrix of real rank $n$ with every square submatrix sized at least ${n^{\gamma}}\times{n^{\gamma}}$ distinct for some fixed $\gamma>0$? Upper Bounds: Number ...
user avatar
4 votes
1 answer
814 views

Existence of triangle-free graphs for regular graphs of degree at most n/2

It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to half the number of vertices (...
Gizem's user avatar
  • 43
4 votes
1 answer
924 views

What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...
blt's user avatar
  • 1,203
4 votes
3 answers
888 views

Maximal pairwise distance between $k$ permutations

How can k permutations on n-set be arranged to maximize minimal pairwise Kendall tau distance (i.e. number of discordant pairs) between them? For two permutations this is obviously when the second ...
Bogdan Chornomaz's user avatar
4 votes
2 answers
381 views

An extremal combinatorics problem

Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ what is the largest $m$ we have such that in the interval $(p^\alpha,p-p^\alpha)$ there are $m$ integers $a_1<\dots<a_m$ ...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
236 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
Turbo's user avatar
  • 13.7k
3 votes
0 answers
110 views

Minimum number of couples of sets with non-empty intersection in a union closed family

Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element ...
Fabius Wiesner's user avatar
3 votes
2 answers
283 views

Choosing subsets to cover larger sets

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ ...
boaten's user avatar
  • 175
2 votes
1 answer
193 views

Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement: If $n \leq 4$ is a natural number, if $\mathcal{F}$ is a union-closed family of non-empty sets, if the universe of $\mathcal{F}$ (i.e. ...
Panurge's user avatar
  • 1,215
1 vote
1 answer
140 views

Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$

Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square. Through the determinant ...
Turbo's user avatar
  • 13.7k
0 votes
0 answers
101 views

Lower bound for couples of disjoint sets in some partitions of the power set

Originally posted on MathStackExchange but without answers. Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n])...
Fabius Wiesner's user avatar
0 votes
0 answers
174 views

Another conjecture about couples of disjoint two-element sets

Let $\{A_1,B_1\},\ldots,\{A_k,B_k\}$ be all the distinct unordered couples of subsets, with $A_i \cap B_i = \emptyset, 1 \le i \le k$, that can formed from a set $\{C_1,\ldots,C_q\}$, $q \le \binom{n}{...
Fabius Wiesner's user avatar
0 votes
0 answers
100 views

Number of $b$-separated Sidon sets with pairwise difference set intersection bounds

Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ call a set of $m$ integers $a_1<\dots<a_m$ in the interval $(p^\alpha,p-p^\alpha)$ to be $b$-separated Sidon if: $a_i-a_j\...
Turbo's user avatar
  • 13.7k