Questions tagged [extremal-combinatorics]
The extremal-combinatorics tag has no usage guidance.
206
questions
5
votes
1
answer
189
views
How many base elements can a sunflower-free system have?
A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdős and Rado says that there is a constant $C_t$ such ...
2
votes
0
answers
77
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 $...
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$ ...
5
votes
2
answers
425
views
Minimum number of transpositions to make two multiset permutations equal
I think this problem should have a known solution, but I wasn't able to find any reference.
Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.
...
5
votes
2
answers
631
views
Minimum number of swaps to make multisets elements sums close
This problem was originally posted at math.stackexchange but there is no answer there, even after a (now expiring) bounty.
Choose $4$ multisets of size $n$ with elements $x \in \mathbb{R}$, $0 \le x \...
1
vote
1
answer
66
views
Lower bound for the sum of the number of vertices of some subgraphs of a directed graph
Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.
Let $C(V_i)$ be the union of ...
7
votes
1
answer
368
views
Large sets of nearly orthogonal integer vectors
This question is motivated by the Question 5 from the 2017 Asia Pacific Mathematical Olympiad. To paraphrase, the question asks what is the largest cardinality of a set $S \subset \mathbb{Z}^n$ such ...
0
votes
0
answers
21
views
From average degree to a highly connected subhypergraph
I'm looking for a result in $k$-uniform hypergraphs analogous to the following result for graphs, due to Mader:
Every graph of average degree $4r$ has a $r$-connected subgraph.
0
votes
0
answers
69
views
Large family of subsets with small pairwise intersections
(Crossposting from StackExchange 4799692 after it has been there for a while.)
Let $\alpha>0$ be a constant (can be sufficiently small if necessary) and $n$ be sufficiently large. What can we say ...
8
votes
0
answers
213
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 ...
3
votes
2
answers
254
views
Continuous version of the union-closed sets conjecture
Let $F = \{f_1, \ldots, f_n\}$ be a set of continuous functions $f_i: [0,1] \rightarrow [0,1]$,
$i = 1, \ldots, n$, such that $f_i \in F \land f_j \in F \implies \max(f_i,f_j) \in F$.
I would like to ...
8
votes
1
answer
207
views
Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?
The Heawood graph is a $3$-regular graph on $14$ vertices. Its (adjacency) spectrum is $\{ (3)^1, (\sqrt{2})^6, (-\sqrt{2})^6, (-3)^1 \}$. So, $3/7 \approx 42.8\%$ of its eigenvalues equal $\sqrt{2}$.
...
2
votes
1
answer
191
views
Conjecture about families of subsets of $\{1,\ldots,2n+1\}$ of size $n+1$
Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n+1$, $n \ge 1$. The size of $\mathcal{A}$ is therefore $\binom{2n+1}{n+1}$.
For any family $\mathcal{...
4
votes
0
answers
95
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., ...
0
votes
0
answers
174
views
Another conjecture about couples of disjoint two-element sets
Let $\{A_1,B_1\},\ldots,\{A_k,B_k\}$ be all the distinct unordered couples of subsets, with $A_i \cap B_i = \emptyset, 1 \le i \le k$, that can formed from a set $\{C_1,\ldots,C_q\}$, $q \le \binom{n}{...
0
votes
0
answers
110
views
Simpler lower bound for couples of disjoint sets
This is similar to a previous question, but simpler, I suppose.
Let $\mathcal{B}$ be the family of all subsets of $[n]=\{1,2,\ldots,n\} $ of size $2$. Let $\mathcal{F} = \{\mathcal{A}_1,\ldots,\...
0
votes
0
answers
100
views
Lower bound for couples of disjoint sets in some partitions of the power set
Originally posted on MathStackExchange but without answers.
Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n])...
0
votes
0
answers
25
views
Maximum sizes of independent sets in (non-uniform) hypergraphs
It is a very well understood problem to compute the size of the maximum independent set in a uniform hypergraph (in terms of extra conditions).
My question is the following: what is known for ...
8
votes
1
answer
416
views
When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?
Firstly, this question has been posted to Math StackExchange with no complete answer so far.
Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will ...
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 $\...
6
votes
2
answers
780
views
Conjecture about partitions of the powerset without the empty set
I would like to have some ideas about possibilities of proving or disproving the following conjecture:
For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without ...
11
votes
1
answer
641
views
A variant of the corners problem
Question: What is the size of the largest subset of $[n]^2$ containing no three point configurations of the form $(x,y), (x,y+d), (x+d,y')$ with $d \neq 0$? In particular, is it at most $O(n)$?
Recall ...
1
vote
2
answers
124
views
Regarding a specific Turán number of graphs
I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...
1
vote
1
answer
121
views
Counting $K_{2, 2, \,\ldots\,,2}$ in a $k$-partite $k$-uniform hypergraph
Let $G$ be a $k$-partite $k$-uniform hypergraph with at least $dn^k$ many edges. I want a lower bound on the number of $K_{2, 2,\, \ldots\,,2}$ in $G$, preferably something like $\gamma n^{2k}$ for ...
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, ...
1
vote
1
answer
86
views
How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?
I have a $k$-partite $k$-uniform hypergraph $H$ with $V(H) = V_1 \cup\cdots\cup V_k$ (each $|V_i|=n$ for $i \in [k]$), such that the minimum vertex degree $\delta(H) \ge Cn^{k-1}$ for a constant $C$. ...
1
vote
1
answer
116
views
Extremal graph theory - many copies of $K_r$ imply a copy of $r$-chromatic $H$
I know that it must be a simple consequence of the Kővári–Sós–Turán (and Erdős–Stone) theorem, but I am struggling to formulate a proof: Let $H$ be a fixed-size $r$-chromatic graph. Then there exists $...
0
votes
2
answers
302
views
Reference for a topological result
I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
0
votes
0
answers
127
views
On nilpotent singular $\mathbb F_2^{n\times n}$ matrices
Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$.
The set of such singular matrices form a semigroup.
The set of nilpotent matrices of size $n\times n$ form a semigroup.
...
6
votes
1
answer
256
views
A Sauer-Shelah-like lermma for prefix tree
I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known.
Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
0
votes
0
answers
349
views
Union-closed family with a certain property
Now crossposted at math.stackexchange.
Consider a union-closed family $\mathcal{F} = \{A_1, \dotsc ,A_n\}$ of $n$ finite sets, $n$ odd, $n \ge 3$, $A_i \neq \emptyset$, $i=1,\dotsc,n$.
Let $r=\frac{n+...
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 ...
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 ...
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 ...
6
votes
1
answer
180
views
Graphs without short cycles and with linear number of edges
Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...
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 ...
2
votes
1
answer
143
views
Bounds for $\mathrm{ex}(n,K_{2,\dots,2}^{(r)})$
$\DeclareMathOperator\ex{ex}$We write $K_{2,\dots,2}^{(r)}$ to denote the $r$-uniform hypergraph with vertex set $\{1,2\}\times\{1,\dots,r\}$ and hyperedge set $\{(1,1),(1,2)\}\times \{(2,1),(2,2)\} \...
6
votes
2
answers
385
views
Coloring of a graph representing the power set
For a positive integer $n$, let $\mathcal{P}$ be the power set of $[n]$. Consider the graph $G$ with $\mathcal{P}$ as its vertex set, and, for $S_1,S_2 \in \mathcal{P}$, the edge $(S_1,S_2)$ exists ...
1
vote
0
answers
94
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+\...
1
vote
1
answer
140
views
$n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?
The coloring game is a game played between Alice and Bob.
There exists a grid of size $n \times n$, where $n$ is a strictly positive integer.
Each cell of the grid can be colored with a color that ...
3
votes
1
answer
191
views
Extremal problems in additive combinatorics (over finite fields)
As you may know, there has been very recently a big breakthrough concerning upper bounds for the capset problem over $\mathbb{F}_3^n$ (and further generalizations to $\mathbb{F}_q^n$). I was wondering ...
26
votes
3
answers
866
views
What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple ...
1
vote
1
answer
163
views
Chromatic number or independence number of the generalized Kneser Graph
For positive integers $n,k$ and $s$, where $0\le s<k$ and $k \le n$, we define the generalized Kneser graph $K(n,k,s)$ as follows: The vertices of $K(n,k,s)$ are the $k$-subsets of $[2n]$, i.e., we ...
3
votes
1
answer
553
views
Sum of $q$-binomial coefficients
Denote by $ \binom{n}{k}_q = \prod_{i=0}^{k-1} \frac{ q^{n-i} - 1 }{ q^{k-i} - 1 } $, $ k = 0, 1, \ldots, n $, the $ q $-binomial (Gaussian) coefficients. These numbers are symmetric, in the sense ...
5
votes
2
answers
407
views
Counting intersections of hyperplanes
This is a dublicate from stackexchange:
Consider two families of hyperplanes $F_1$ and $F_2$ in $\mathbb{R}^d$ both containing $n$ hyperplanes. We have that for all $f \in F_1$ and $g \in F_2$ that $f$...
1
vote
0
answers
122
views
Probability puzzle on partitions
Consider a set $U$ of size $n$ and let $\mathcal{S}$ be the set of all $(n/2)$-subsets of $U$ (assume $n$ is divisible by 4). Let $P$ be a partition of $\mathcal{S}$ into $k$ blocks $B_1,\dots,B_k$.
...
4
votes
0
answers
157
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 ...
1
vote
0
answers
103
views
Number of intersections that must occur in any partition of a given size
Let $\mathcal{S}$ be the set of all $n$-element subsets of $[2n]:=\{1,\dots,2n\}$.
Consider a partition $\mathcal{P}$ of $\mathcal{S}$ into $m$ blocks $P_1,\dots,P_m$, where all except at most one of ...
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: ...