Questions tagged [extremal-combinatorics]
The extremal-combinatorics tag has no usage guidance.
134
questions
5
votes
1answer
209 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
0answers
38 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
1answer
49 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
1answer
70 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]$ ...
0
votes
0answers
53 views
Extremal thresholds of balancing integer vectors by linear transformation
Take $v$ to a vector in $\mathbb Z^m$ with entries from $0$ to $2^k-1$ (there are $2^{km}$ possible vectors).
Define $L(v)$ to be difference between the largest and the smallest entries in $v$ and ...
2
votes
0answers
34 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
vote
0answers
107 views
Game on the boolean cube?
Alice and Bob play a game on the boolean cube in $n$ dimensions.
Alice: Picks $\leq 2^{n-1}$ $0/1$ points and gives to Bob.
Bob: Pick minimal number $f(n)$ halfspace inequalities each describable by ...
4
votes
1answer
144 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
0answers
31 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
0answers
78 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
0answers
181 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
0answers
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
0answers
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 ...
30
votes
3answers
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
2answers
722 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
0answers
59 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
0answers
59 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 ...
4
votes
0answers
120 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
1answer
195 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 ...
7
votes
1answer
315 views
A proper definition of connectivity for hypergraphs
For usual graphs on $n$ vertices, a edge-minimal connected graph is nothing but a spanning tree of this graph. It is well-known that any spanning tree has $n-1$ edges.
I would like to know whether ...
3
votes
1answer
104 views
The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Let $c(n,k)$ be the least integer such that if $G$ is a simple graph on $n$ vertices with $n + c(n,k) - 1$ edges then $G$ has $k$ edge-disjoint cycles.
Clearly, $c(n, 1) = 1$ and it not very hard to ...
4
votes
0answers
87 views
Minimum number of balanced partitions
For any multiset $x_1,x_2,\ldots,x_{2n}$ of positive real numbers, a partition into two nonempty subsets $(A,B)$ is called "balanced" if $\text{sum}(A)\geq\text{sum}(B)-\max(B)$ and $\text{sum}(B)\geq\...
0
votes
0answers
92 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\...
4
votes
2answers
349 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$ ...
2
votes
0answers
45 views
Is the finite projective plane stable as an extremal set system?
Let $\Sigma$ be a set of $|\Sigma| = n$ subsets of the universe $[n]$, each of size $k$, with the property that any two of these subsets intersect on at most one element. It is easy to see that the ...
2
votes
1answer
118 views
Distinguishing points by sets of given size
The problem is:
Given a finite set $X$ with size $x$ and let $B$ denote a family of $k$-element subsets of $X$, called blocks. What is the smallest possible number $n$ of blocks such that every ...
3
votes
0answers
84 views
chromatic number of plane using Cairo pentagonal tiling
Scale the Cairo pentagonal tiling so the short side is of length 1. Then it is easy to colour the tiling with 8 colours, two parallel ribbons of four colours each, to establish that the chromatic ...
19
votes
0answers
350 views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
1
vote
2answers
150 views
Extremal density of a graph without a non-backtracking $2k$-cycle
The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form
$$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$
while the ...
8
votes
1answer
250 views
A generalization of Erdős-Ko-Rado theorem
Is there any result known about the following generalization of the Erdős-Ko-Rado theorem?
Let $n, k, r, s$ be positive integers. We call a family $\mathcal{F}$ of $k$-element subsets of $\{1,\ldots, ...
2
votes
1answer
71 views
If we take a small subset of a sparse/uniform set system, how uniform can we arrange for the subset to be?
Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements ...
1
vote
1answer
96 views
Number of distinct 3-sets formed as subsets of a 4-uniform set family
Let $\mathcal{F} \subseteq \binom{[n]}{4}$ be a collection of size-4 subsets of $\{1,\ldots,n\}$, i.e., a 4-uniform set family.
Let $\mathcal{F'}$ be the collection of size-3 sets for which a ...
3
votes
0answers
74 views
Szemeredi-Trotter bounds when the lines are implicitly described by a point set
Recall:
Theorem (Szemeredi-Trotter): Given $n$ distinct points and $\ell$ distinct lines in $\mathbb{R}^2$, the number of point-line incidences is $O(n + \ell + (n \ell)^{2/3})$.
Now, instead of $\...
2
votes
1answer
107 views
Abundance in union closed families
For any finite set $S$ and every partition $S_1, \dots, S_n$ of $S$, let $P(S_1, \dots, S_n)$ be the family consisting of all possible unions of $S_1, \dots, S_n$. Clearly, $P(S_1, \dots, S_n)$ is a ...
3
votes
1answer
159 views
Cardinality of families of (almost) disjoint subsets
Let $G = \{1, 2, \ldots, n\}$ be the ground set. What is the maximum number of subsets of size at least $n/3$ of $G$ where any two subsets have at least $n/10$ different elements?
I am interested in ...
2
votes
0answers
110 views
Number of distinct rows and columns in a matrix with bounded number of entries
How many distinct rows and columns a real square matrix can have (at least in symmetric case) such that rank of matrix is $r$ and entries:
are from $\{-b,-b+1,\dots,0,\dots,b-1,b\}$?
are from $\{-b,-...
2
votes
0answers
90 views
On a random matrix construction
Given a symmetric matrix $M\in\Bbb Z^{n\times n}$ or rank $r$ with absolute value of any entry bound by $2^{b^2-1}-1$ and maximum eigenvalue at most $\lambda$.
We consider the set $\mathcal T_b$ of $\...
1
vote
0answers
109 views
On the complexity of writing down matrices
Consider families of $0/1$ matrices in $\Bbb B$ where $1+1=1$:
$\mathcal M_{1,n,c}$ contains $2^n\times 2^n$ matrices that can be written as Hadamard product of $t=O(2^{(\log n)^c})$ matrices $$(J_n-...
0
votes
1answer
129 views
On sum of matrices
Suppose we have a matrix $M\in\Bbb Q^{n\times n}$ with no $0$ elements and we write as sum of two matrices $M_1$ and $M_2$ on following constraint.
$M_{1,ij}=M_{ij}$ and $M_{2,ij}=0$ or $M_{1,ij}=0$ ...
3
votes
0answers
92 views
How many positions of a tile can occur in a periodic tiling?
In my recent question about polygonal tilings where tiles can occur in infinitely many positions, both constructions given as solutions are of self-similar nature. This means in particular that there ...
1
vote
1answer
108 views
Are there polygonal tilings with infinitely many positions, each (or at least one) occurring infinitely often?
My recent question about polygonal tilings where tiles can occur in infinitely many positions has been answered by two nice constructions (besides Jan Kyncl's answer, there is the Conway tessellation ...
9
votes
1answer
257 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 ...
3
votes
0answers
59 views
Rank relation to maximum subpermanent and subdeterminant?
Given a $\pm1$ matrix $M$ of rank $r$ let the largest subdeterminant be $d$ and let the largest subpermanent be $p$.
Are there relations/bounds that connect $r$, $d$ and $p$?
Are there geometric and ...
3
votes
1answer
208 views
What does this permutation polynomial look like?
What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?
Are there good ...
10
votes
3answers
474 views
Positive integer combination of non-negative integer vectors
A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and ...
1
vote
0answers
110 views
Expectation of a combinatorial extremal random variable?
Consider the finite set $\chi(D)$ of all sets of integer points in $\Bbb Z^n$ around origin which have distance at most $D$ from each other and pick a set $\mathcal P(D)$ from set of sets $\chi(D)$ ...
2
votes
0answers
53 views
Totally distance non-preserving transformations
JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)
guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...
13
votes
2answers
295 views
Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B $
This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered ...
3
votes
0answers
91 views
Generalization of fisher inequality
What upper bounds are known on the size of a family $\mathcal{S}$ of subsets $S_i \subset [N]$ such that:
i) each $S_i$ is of size $pk$.
ii) for $i \neq j$, $|S_i \cap S_j| \bmod p \in U$, for some ...
2
votes
0answers
57 views
An extremal problem in directed path systems
The following is a common rephrasing of the well-known open problem in extremal graph theory to (asymptotically) determine $ex(n, C_8)$:
What is the asymptotically maximum $L = L(n)$ such that ...
