Questions tagged [extremal-combinatorics]
The extremal-combinatorics tag has no usage guidance.
79
questions with no upvoted or accepted answers
21
votes
0
answers
425
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, ...
10
votes
0
answers
183
views
Number of triangle-free graphs with prescribed number of edges
This question is posted from StackExchange since it received no answer there.
Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
8
votes
0
answers
214
views
A variation of necklace splitting
Our problem is the following:
Let $n$ and $k$ be integers.
We are given two (unclasped) necklaces, each with $n$ colored stones: a top necklace which has $k$ colors and a bottom necklace which has 2 ...
8
votes
0
answers
1k
views
The state of art of the sunflower lemma
I am interesting in the sunflower system and its applications in computer science.
Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...
7
votes
0
answers
169
views
Szemerédi's regularity lemma for binary operations
Szemerédi's regularity lemma is an approximate structure theorem for
all large graphs (symmetric binary relations). There are versions for
multicolored graphs and directed graphs. Is there an ...
7
votes
0
answers
108
views
A question related to the union-closed sets conjecture
Let $f(n)$ denote the maximum possible cardinality of a collection $\mathcal F$ of nonempty sets which is closed under unions ($X,Y\in\mathcal F\implies X\cup Y\in\mathcal F$) and is such that no ...
5
votes
0
answers
129
views
Exponential bound for very weak sunflowers?
Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them.
A family of sets is r-diverse if any $r$ of its members are diverse.
Is there for every $r\ge 3$ ...
5
votes
0
answers
171
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 ...
5
votes
0
answers
104
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\...
5
votes
0
answers
161
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$....
5
votes
0
answers
234
views
A combinatorial problem
What is the largest $m\times m$ $0/1$ matrix of real rank $n$ with every square submatrix sized at least ${n^{\gamma}}\times{n^{\gamma}}$ distinct for some fixed $\gamma>0$?
Upper Bounds: Number ...
5
votes
0
answers
179
views
Families of Sets with Two Intersection Numbers
Let $k$ and $n$ be natural numbers. Let $I$ be a set of natural numbers. Let $\mathcal{F}$ be a family of $k$-element subsets of $\{ 1, \ldots, n\}$ such that $A, B \in \mathcal{F}$, $A \neq B$, ...
5
votes
0
answers
226
views
Diameter of subset sum graph
We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...
4
votes
0
answers
96
views
What properties do graphs avoiding large regular subgraphs have?
Fix a positive integer $r$ and real $\delta \in (0,1)$.
Let $G$ be an undirected graph on $n$ vertices. Suppose that $G$ does not contain an $r$-regular subgraph on at least $\delta n$ vertices (i.e., ...
4
votes
0
answers
219
views
Weight transfer proof of Turán’s theorem
Turán’s theorem, which states that a $K_{p+1}$-free graph contains at most $(1-1/p)\frac{N^2}{2}$ edges, can be proven in many different ways, as pointed out, for example in M. Aigner, G. M. Ziegler, ...
4
votes
0
answers
80
views
Bounding the Betti numbers of Čech complexes in Euclidean space
Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \ge 2$. Then let $C=C(S)$ denote the union of closed balls of radius $1$ centered at points of $S$.
For $0 \le j \le d-1$, how large can the ...
4
votes
0
answers
158
views
Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?
This is not a concrete question, just some thoughts.
The Komlos Conjecture is as follows-
There exists an absolute constant $C>0$, such that the following holds:
For all $d$ and any set of vectors ...
4
votes
0
answers
103
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
4
votes
0
answers
93
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 ...
4
votes
0
answers
82
views
Cases of equality in Daykin's theorem
Let $A$ and $B$ be sets of subsets of $\{1, \dots, n\}$, and let $A \wedge B = \{a \cap b : a\in A, b\in B\}$, $A\vee B=\{a\cup b: a\in A, b\in B\}$. Then
$$
|A \wedge B| |A\vee B| \geq |A||B|,
$$
as ...
4
votes
0
answers
114
views
Kruskal-Katona for homocyclic groups?
I need a version of the Kruskal-Katona theorem (better still, of the Lovasz "approximate" version thereof) for the elementary abelian / homocyclic groups, in the following spirit:
What is the ...
3
votes
0
answers
110
views
Minimum number of couples of sets with non-empty intersection in a union closed family
Every union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, must have at least $\frac{2}{3}\binom{n}{2}$ unordered couples of sets with at least one element ...
3
votes
0
answers
86
views
Harper's theorem on the general Hamming graph
Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$ (i.e., the set of vertices that have neighbors in $S$). The vertex expansion of $G$ is
$$ \min_{S\subseteq ...
3
votes
0
answers
92
views
Minimum number of partitions of a set such that the same pair must occur in a block in at least half of them
For positive integers $k$ and $n$, let ${S} = \{1,\dots,k\ n\}$. Consider $\ell \ge 3$ partitions $P_1,\dots,P_\ell$ of ${S}$, where each $P_i$ splits ${S}$ into $n$ blocks all of size $k$.
Question: ...
3
votes
0
answers
70
views
Boundary differences in two graphs
Let $\Gamma, \Xi$ be two graphs with the same set of vertices $V$ with $n$ elements. Assume $\Gamma$ is connected. Write $\Gamma\cup \Xi$ (or $\Gamma\cap \Xi$) for the graph whose set of edges is the ...
3
votes
0
answers
108
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 ...
3
votes
0
answers
101
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 $\...
3
votes
0
answers
106
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 ...
3
votes
0
answers
103
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
0
answers
114
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 ...
3
votes
0
answers
66
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 ...
3
votes
0
answers
183
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 ...
3
votes
0
answers
132
views
Kruskal-Katona for multisets?
Following Fedor Petrov's remarks, here is a "set-theoretic version" of the
question I asked a while ago.
For integer $n\ge 1$, denote by $\mathcal M_n$ the family of all (finite)
multisets with the ...
3
votes
0
answers
236
views
Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method
The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time.
(1) Is there any ...
3
votes
0
answers
102
views
What is the maximal number of partitions with this maximal intersection property?
Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...
2
votes
0
answers
78
views
A variant of the social golfer problem and the kirkman schoolgirl problem
I came across the following simple question that seems to be open:
Let $U$ be a set of $n$ elements.
Let $P_1$ be a partition of $U$ into $k\le n$ "blocks" (i.e. disjoint subsets) and let $...
2
votes
0
answers
129
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\...
2
votes
0
answers
185
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 ...
2
votes
0
answers
87
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 ...
2
votes
0
answers
59
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
0
answers
120
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
99
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 $\...
2
votes
0
answers
58
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 ...
2
votes
0
answers
83
views
Euclidean minimum spanning trees intersecting each unit square
The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an $n\...
2
votes
0
answers
95
views
On subset of Deterministic games
Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...
2
votes
0
answers
437
views
combinatorial rectangles
Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.
Is there ...
1
vote
0
answers
44
views
How small must partitions be to ensure overlapping blocks?
Consider the set family $F$ of all $t$-element subsets of $[n]$, for some positive integer $n$.
Let $P_1$ be a partition of $F$ into $k$ blocks.
Let $P_2 \ne P_1$ be another partition of $F$ into $k$ ...
1
vote
0
answers
107
views
Improved conjecture about partitions of the powerset without the empty set
This conjecture is similar to the previously disproved one, but more difficult.
For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without the empty set element $\...
1
vote
0
answers
60
views
Lower bound for the minimum of the maximum frequency of an element - with restrictions
Consider a family $\mathcal{F}$ of non-empty sets, with
$n=|\mathcal{F}|$ sets, $q=\left|\cup\mathcal{F}\right|$ elements in the universe, and $q\le n/4$.
It is known that of the $\binom{n}{2}$ ways ...
1
vote
0
answers
95
views
cone structure of complement of hyperplanes
I want to know if in $\mathbb{R}^{m+3}$ we consider the following hyperplanes:
\begin{cases}
(1-g)y-\sum_{i\in I}x_i=0, & \text{if $I\subset\{1,\cdots,m+2\}$},|I|=g\\
gy-\sum_{i\in I}x_i+\...