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+\...
- 311
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 ...
- 11
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 ...
- 1,054
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 ...
- 369
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 ...
- 425
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$...
- 143
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$.
...
- 11
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 ...
- 141
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: ...
- 31
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}...
- 185
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=...
- 418
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 ...
- 61
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 \...
- 874
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 ...
- 471
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 ...
- 881
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 ...
- 43
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 ...
- 12.8k
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$ ...
- 143
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., $ \...
- 425
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 $|...
- 1,246
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$ ...
- 1,179
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$...
- 143
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$ ...
- 17.1k
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 ...
- 43.7k
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 ...
- 8,573
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$-...
- 121
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 ...
- 16.7k
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 ...
- 725
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,663
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 ...
- 426
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,328
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 ...
- 1,054
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 ...
- 3,379
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,598
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\...
- 1,349
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?
...
- 12.8k
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 ...
- 12.8k
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}...
- 1,173
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 ...
- 227
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 ...
- 12.8k
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 ...
- 12.8k
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 ...
- 4,003
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$ ...
- 228
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 ...
- 1,708
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 ...
- 1,537
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 ...
- 18.6k
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 ...
- 30.7k