# Questions tagged [extremal-combinatorics]

The extremal-combinatorics tag has no usage guidance.

208
questions

0
votes

0
answers

26
views

### Does there exist a Graph Counting Lemma in the Cut density condition?

Background: In http://dx.doi.org/10.1016/j.ejc.2011.03.011 Lem9.3 Svante Janson proved that let $0<p<1$ and graphon $W$ with $\int W=p$, if for any subset $A\subseteq\left[0,1\right]$ it holds $\...

0
votes

0
answers

34
views

### Does this "linear-approximated" version of Graph Counting Lemma hold?

Let $0\leq d\ll\varepsilon,\frac{1}{e},\frac{1}{v}\leq 1.$ Let $G$ be a $n$-vertices graph ($n$ is sufficient large, $1/n\ll d$) and for any $A,B\subseteq V(G)$, the edge density $d(A,B)\geq d.$ Then ...

5
votes

1
answer

198
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

79
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

468
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

635
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

67
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

374
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

70
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

217
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

255
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

213
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

192
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

97
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

101
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

426
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

783
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

660
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

131
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

122
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

224
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

118
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

303
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

128
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

258
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

352
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

111
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

185
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

184
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

386
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

96
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

195
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

867
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

167
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

562
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

418
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

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