Questions tagged [extremal-combinatorics]
The extremal-combinatorics tag has no usage guidance.
0
votes
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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 ...
