Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 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
194 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 ...
5 votes
2 answers
434 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$. ...
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 ...
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 ...
1 vote
2 answers
125 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 ...
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 $...
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$ ...
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 ...
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
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 ...
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
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 ...
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+...
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{...
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,\...
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., ...
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
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
419 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 ...
6 votes
3 answers
506 views

Partitioning the 3-sets of [n]={1,...,n} into families

Let $F_1,...,F_m$ be a partition of the 3-element subsets of $[n]$ into families such that no three subsets in any one family $F_i$ are all contained in one 4-element subset of $[n]$. What is the ...
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 ...
50 votes
7 answers
3k views

Dividing a cake between $n-1$, $n$, or $n+1$ guests

A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be $n-1$, $n$, or $n+1$. What is the minimal number $f(n)$ of pieces the cake ...
11 votes
1 answer
646 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
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
220 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
117 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
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
257 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 ...
2 votes
1 answer
287 views

Do sparse graphs contain a single regular pair?

An easy corollary of the Szemerédi Regularity Lemma is that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. As noted ...
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
182 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 ...
26 votes
2 answers
2k views

What is the best lower bound for 3-sunflowers?

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 Erdos and Rado says that there is a constant $C_t$ such ...
55 votes
1 answer
3k views

Intersecting family of triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
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 ...
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)\} \...
3 votes
2 answers
279 views

Rank changes with matrix edits

Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric). Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix. Case $1$: $M+W\in\{0,1\}^{n\times n}$. Could ...
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 ...
21 votes
3 answers
3k views

Cauchy-Schwarz proof of Sidorenko for 3-edge path (Blakley-Roy inequality)

Is there a "Cauchy-Schwarz proof" of the following inequality? Theorem. Given $f \colon [0,1]^2 \to [0,1]$, one has $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \,...
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
2 3 4 5