# Questions tagged [extremal-combinatorics]

The extremal-combinatorics tag has no usage guidance.

134
questions

**5**

votes

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

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

**30**

votes

**3**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

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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