Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [extremal-combinatorics]

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