# Questions tagged [extremal-combinatorics]

The extremal-combinatorics tag has no usage guidance.

**0**

votes

**0**answers

74 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

300 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

38 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

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

**0**

votes

**0**answers

26 views

### Maximum possible crossing number of a restricted tangle family

Let $T$ be a tangle (in the sense of knot theory) on $s$ strands and no loops. In general the crossing number of $T$ is unbounded, as we can twist two strands around each other any number of times. ...

**3**

votes

**0**answers

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

**16**

votes

**0**answers

249 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

139 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

205 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

67 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

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

**2**

votes

**0**answers

51 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

101 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

149 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

104 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

84 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

105 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

127 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

86 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

102 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

207 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

46 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

204 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

364 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

100 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

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

**12**

votes

**2**answers

260 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

73 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

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

**0**

votes

**1**answer

88 views

### Erdős-Ko-Rado with intersections of size at least two

Up to how many subsets of $\{1,2,\dots,2n\}$ of size $n$ can we choose so that each pair has an intersection of size at least two?
The original Erdős-Ko-Rado paper shows that taking all subsets that ...

**4**

votes

**2**answers

160 views

### Lower bounds on size of unique cover?

Given a universe $U = \{e_1 , . . . , e_n\}$ of
elements, and given a collection $S = \{S_1 , . . . , S_m \}$ of subsets of $U$, each of size $\le k$, the subcollection $S' \subseteq S$ is a unique ...

**3**

votes

**1**answer

167 views

### Graph properties that imply a bounded number of edges

Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...

**8**

votes

**1**answer

237 views

### For an intersecting family of $m$ sets there are at least $2m$ sets that are contained in at least one of them

Let $F$ be a finite family of non-empty sets such that any two of them intersect. Consider the set $F'$ consisting of all sets that are a subset of at least one element of $F$. Prove $|F'|\geq 2|F|$.
...

**4**

votes

**0**answers

71 views

### Are extremal tournament matrices always circulant or 'almost circulant'?

Define an antisymmetric 1-x-matrix as an $n\times n$ matrix $M=(m_{ij})$ with $m_{ii}=0$ and $\{m_{ij},m_{ji}\}=\{1,x\}$ for all $1\le i<j\le n$. Call their set $\mathcal A_n$.
The setup is as ...

**3**

votes

**0**answers

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

**5**

votes

**0**answers

100 views

### A Combinatorial Problem on Extremal Set Theory

Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?
(i) $\forall S\in \mathcal{F}$, $|S|=a$....

**4**

votes

**1**answer

79 views

### Maximal number of perfect matchings that pairwise form a Hamiltonian cycle

Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.
Question: Is it true that $...

**4**

votes

**1**answer

264 views

### Orchard-planting problem in space

The original orchard-planting problem asks for the maximum number of $3$-point lines attainable by a configuration of points in the plane. I am interested in its natural generalization for (three-...

**0**

votes

**0**answers

143 views

### A Non-trivial intersecting set system problem

Liven large enough $k\in\Bbb N$ fix $m\in\{2,3,\dots,k\}$ and fix $4k$ cardinality set $K_{4k}$.
What is the maximum $n\in\Bbb N$ such that at some $t\geq2n-1$ there are $$\mbox{ subsets }L_1,L_2,\...

**14**

votes

**3**answers

425 views

### How few $k$-dimensional subspaces of $V$ are enough to have a complement to each $n-k$-dimensional subspace?

Let $n$ and $k$ be nonnegative integers such that $k\leq n$. Let $F$ be a field, and let $V$ be an $n$-dimensional $F$-vector space. A set $\mathcal{S}$ of $k$-dimensional subspaces of $V$ is said to ...

**7**

votes

**1**answer

193 views

### How to find a permutation of [n] so that $\sum\{\min(i-l[i],r[i]-i)\}$ is maximized?

Given a sequence $a_1, a_2,\dots,a_n$, define the two sequences
$$l_i=\max_{1 \leq j < i, a_j \geq a_i} j$$
or $0$ if it does not exist; and
$$r_i=\min_{i < j \leq n, a_j > a_i} j$$
or $n+...

**0**

votes

**1**answer

118 views

### Unavoidable finite set for infinite k-intersecting family?

Suppose we have a family $F$ such that:
For each $A \in F$ we have $|A| = k$ and $A \subset n$.
For each $A,B \in F$ we have $A \cap B \neq \emptyset$.
It is easy to show that there exists a ...

**4**

votes

**3**answers

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

**8**

votes

**1**answer

386 views

### On a result of Frankl and Wilson

In the paper 'Intersection theorems with geometric consequences' (Combinatorica 1981) P. Frankl and R. M. Wilson consider families $\mathcal{F}$ of $k$-subsets of $\{1,\dots,n\}$ with the restriction ...

**1**

vote

**1**answer

218 views

### An extremal problem on matrices

Is it possible to determine (or give bounds for) the following extremal problem:
Let $k,m,r$ be positive integers such that $k,m \geq r$. What is the least number $n$ such that for any $r \times n$ ...

**3**

votes

**1**answer

188 views

### Lower bound construction for Multidimensional Szemerédi's Theorem

The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement.
Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is ...

**0**

votes

**0**answers

38 views

### Possible Number of Repetation of a Submatrix

Notation:
$H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...

**2**

votes

**1**answer

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

**0**

votes

**1**answer

155 views

### Reference for Turan Density

I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...

**5**

votes

**1**answer

185 views

### Maximum size of minimal sequence of transpositions whose product is a given permutation

Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...