# Questions tagged [extremal-combinatorics]

The extremal-combinatorics tag has no usage guidance.

166
questions

1
vote

0
answers

77
views

### cone structure of complement of hyperplanes

I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes:
\begin{cases}
(1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\
gy-\sum_{i\in I}x_i+\...

1
vote

1
answer

53
views

### $n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

The coloring game is a game played between Alice and Bob.
There exists a grid of size $n \times n$, where $n$ is a strictly positive integer.
Each cell of the grid can be colored with a color that ...

0
votes

0
answers

35
views

### Extremal problems in additive combinatorics (over finite fields)

As you may know, there has been very recently a big breakthrough concerning upper bounds for the capset problem over $\mathbb{F}_3^n$ (and further generalizations to $\mathbb{F}_q^n$). I was wondering ...

20
votes

2
answers

552
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 ...

1
vote

1
answer

67
views

### Chromatic number or independence number of the generalized Kneser Graph

For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...

3
votes

1
answer

304
views

### Sum of $q$-binomial coefficients

Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...

4
votes

2
answers

232
views

### Counting intersections of hyperplanes

This is a dublicate from stackexchange:
Consider two families of hyperplanes $F_1$ and $F_2$ in $\mathbb{R}^d$ both containing $n$ hyperplanes. We have that for all $f \in F_1$ and $g \in F_2$ that $f$...

1
vote

0
answers

100
views

### Probability puzzle on partitions

Consider a set $U$ of size $n$ and let $\mathcal{S}$ be the set of all $(n/2)$-subsets of $U$ (assume $n$ is divisible by 4). Let $P$ be a partition of $\mathcal{S}$ into $k$ blocks $B_1,\dots,B_k$.
...

4
votes

0
answers

120
views

### Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?

This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...

1
vote

0
answers

84
views

### Number of intersections that must occur in any partition of a given size

Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$.
Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...

3
votes

0
answers

82
views

### Minimum number of partitions of a set such that the same pair must occur in a block in at least half of them

For positive integers $k$ and $n$, let ${S} = \{1,\dots,k\ n\}$. Consider $\ell \ge 3$ partitions $P_1,\dots,P_\ell$ of ${S}$, where each $P_i$ splits ${S}$ into $n$ blocks all of size $k$.
Question: ...

3
votes

2
answers

218
views

### Ramsey-Turán density function is well defined

Define
$$RT(n,K_l,f(n))=ex_l(n,f(n))=\max_G\{e(G): K_l \not\subset G, v(G)=n, \alpha(G)\leq f(n)\}$$
and the Ramsey-Turán density function $f_l:(0,1] \to \mathbb{R}$ as
$$f_l(\alpha)=\lim_{n\to \infty}...

0
votes

1
answer

92
views

### A general Turan-like question

Thinking of an edge as of a $2$-clique, it's natural to consider a slightly more general question than Turan considered in his celebrated theorem: given $r \le k \le n$, what is the maximal possible ...

2
votes

1
answer

165
views

### Maximizing and minimizing the number of positive product $k$-subsets of an $n$-set

The question is simple but require some definitions. I came across resolving a certain inequality. If there is no closed answer is there a related sequence describing the situation?
Let
$$S\ :=\ \{X=...

8
votes

2
answers

774
views

### a Littlewood–Offord-type problem concerning the "cubical lattice"

Fix even $n$ and consider the boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, $f : (x_0, \ldots , x_{n - 1}) \mapsto (x_0 \vee x_1) \wedge (x_2 \vee x_3) \wedge \cdots \wedge (x_{n - 2} \vee ...

3
votes

1
answer

159
views

### Products of Mersenne numbers as sums of real numbers

A Mersenne number is a number of the form $2^k-1$ for some $k \in \mathbb{N}$. Consider the set of $2^n-1$ products of Mersenne numbers
$$M_n=\left\{ \prod_{k\in S} (2^k-1) : S \subseteq [n], S\neq \...

7
votes

1
answer

451
views

### Packing equal-size disks in a unit disk

Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...

1
vote

0
answers

28
views

### Inequality between union-closed families of sets and corresponding upward-closed families

This question is about an inequality for union-closed families of sets related to Frankl's conjecture and a result by Reimer. It relates the union-closed families and corresponding upward-closed ...

4
votes

3
answers

310
views

### Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...

1
vote

1
answer

121
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 ...

3
votes

1
answer

143
views

### Maximum number of subsets in which people co-exist with their friends

Let $P = \{1,\dots,p\}$ be a set of people. Consider partitioning $P$ into two disjoint sets, $A$ (of cardinality $a$) and $A^c = P-A$. Let us index $A$ as $A = \{A_1,\dots,A_a\}$. Each person in $A$ ...

12
votes

1
answer

180
views

### Ternary sequences satisfying $ x_i + y_i = 1 $ for some $ i $

Consider a set of strings $ {\mathcal S} \subset \{0, 1, 2\}^n $ satisfying the following two conditions: 1.) every string in $ {\mathcal S} $ has exactly $ k $ symbols from $ \{0, 1\} $ (i.e., $ \...

3
votes

2
answers

108
views

### For $n$ different sets whose union has size $n+1$ ,can you remove the same point from each set while retaining their difference

Let $(A_i)_{i=1}^{n}$ be $n$ different sets. Say $Z := \bigcup_{i=1}^{n}A_i$.
Q1: Is it true that if $|Z| \gt n$ then you can find $x \in Z$ such that the $(A_i-{x)}$ are still all different?
Q2: If $|...

6
votes

1
answer

221
views

### Permutation function based on subsets

We have some subsets $A_1,\dots,A_k$ of $A=\{1,2,\dots,n\}$. For each permutation $\sigma$ of $A$, define $f(\sigma) = \sum_{i=1}^k g(\sigma,A_i)$, where if the earliest element of $A_i$
in $\sigma$ ...

5
votes

1
answer

153
views

### Minimum number of independent pairs in a matroid

Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$...

5
votes

0
answers

116
views

### Exponential bound for very weak sunflowers?

Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them.
A family of sets is r-diverse if any $r$ of its members are diverse.
Is there for every $r\ge 3$ ...

7
votes

0
answers

153
views

### Szemerédi's regularity lemma for binary operations

Szemerédi's regularity lemma is an approximate structure theorem for
all large graphs (symmetric binary relations). There are versions for
multicolored graphs and directed graphs. Is there an ...

6
votes

0
answers

100
views

### A question related to the union-closed sets conjecture

Let $f(n)$ denote the maximum possible cardinality of a collection $\mathcal F$ of nonempty sets which is closed under unions ($X,Y\in\mathcal F\implies X\cup Y\in\mathcal F$) and is such that no ...

2
votes

1
answer

81
views

### Computation of cyclic van der Waerden numbers

Van der Waerden's theorem gives us a finite number $W(k,r)$ defined as the smallest positive integer $N$ such that for any $n\geq N$, any $r$-coloring of $[n]=\{1,\dots,n\}$ admits a monochromatic $k$-...

3
votes

0
answers

67
views

### Boundary differences in two graphs

Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...

2
votes

1
answer

215
views

### Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...

4
votes

0
answers

93
views

### Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...

1
vote

1
answer

92
views

### Schur triples question

So I've been reading through On the number of monochromatic Schur triples by Datrovsky on finding the minimal number of Schur triples. This means you're trying to 2-colour the set of the smallest n ...

5
votes

1
answer

253
views

### Size of a family of sets of $k$-separated functions over $\{0,1,\ldots,n-1\}$

For $n\ge 1$ we write $[n]$ to denote the set $\{0,1,\ldots,n-1\}$. Let $2^{[n]}$ be the set of all functions from $[n]$ to $\{0,1\}$. Let $\mathcal{F}$ and $\mathcal{G}$ be two nonempty subsets of $2^...

1
vote

0
answers

57
views

### 4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...

0
votes

1
answer

53
views

### Maximal families of equal length intervals consist of equilateral triangles

My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post.
Let $\ n\ $ be a ...

1
vote

1
answer

72
views

### What is the minimal possible size of a subset of this semigroup satisfying the following conditions?

Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:
$\forall a \in P[A]$ ...

2
votes

0
answers

74
views

### How many edges can be in an unbalanced bipartite graph of girth $>6$?

Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$.
There is a simple counting argument called the Moore Bounds that gives
$$|E| = O\...

4
votes

1
answer

154
views

### Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations?
...

1
vote

0
answers

36
views

### Partition complexity measure of the boolean cube?

Given $n$ points $p_1,\dots,p_n$ in $\{0,1\}^d$ my goal is to find $m$ index sets $\mathcal I_1,\dots,\mathcal I_m$ on the condition that each index set is a subset of $\{1,\dots,n\}$ on the ...

1
vote

0
answers

81
views

### Maximum number of ways of splitting a set of points with an hyperplane

Given a set $S$ of $n$ points in $\mathbb{R}^d$, let $D_S$ be the set
$\{\mathbf{v}=|\mathbf{u}-\mathbf{u'}|: \mathbf{u},\mathbf{u'}\in S\}$ (where $\forall i=1,2,\ldots, d$, $\mathbf{v}_i=|\mathbf{u}...

2
votes

0
answers

184
views

### The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...

1
vote

0
answers

20
views

### Do small subsets of $S_n$ subgroups cover almost all permutation configurations of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$.
For ...

1
vote

0
answers

91
views

### Are almost all permutation configurations from $S_n$ covered by small subsets subgroups of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$.
Do we have ...

34
votes

4
answers

1k
views

### Dividing a cake between $n-1$, $n$, or $n+1$ guests

A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be $n-1$, $n$, or $n+1$.
What is the minimal number $f(n)$ of pieces the cake ...

5
votes

2
answers

1k
views

### Cardinality of certain subsets in vector spaces over finite fields

Assume that you have an $n$-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and $F$ is a subset of this vector space which contains $m$ ...

1
vote

0
answers

60
views

### Polytopes that can be efficiently described and efficiently covered by cubes or simplices?

Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...

2
votes

0
answers

72
views

### Restricted Erdos-Ko-Rado theorem reference

Consider a family $\mathfrak{F}$ of $k$ element subsets of $\{1,2,..,n\}$, where $n\geq 2k$, such that any two members of $\mathfrak{F}$ have nonempty intersection. The Erdos-Ko-Rado theorem asserts ...

5
votes

0
answers

148
views

### Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...

6
votes

1
answer

277
views

### An inequality for rearrangement-style sums

The following is a holdover from my math contest days that I never got around
to solve.
We will use the notation $\left[ k\right] $ for the set $\left\{
1,2,\ldots,k\right\} $ whenever $k$ is a ...