Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
domotorp's user avatar
  • 18.3k
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 $...
SetFamilyStudent's user avatar
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$ ...
SetFamilyStudent's user avatar
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$. ...
Fabius Wiesner's user avatar
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 \...
Fabius Wiesner's user avatar
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 ...
Fabius Wiesner's user avatar
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 ...
Stanley Yao Xiao's user avatar
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.
kleinbottle's user avatar
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 ...
DesmondMiles's user avatar
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 ...
Sam King's user avatar
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 ...
Fabius Wiesner's user avatar
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}$. ...
The Amplitwist's user avatar
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{...
Fabius Wiesner's user avatar
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., ...
Naysh's user avatar
  • 455
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}{...
Fabius Wiesner's user avatar
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,\...
Fabius Wiesner's user avatar
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])...
Fabius Wiesner's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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 ...
Mohannad Shehadeh's user avatar
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 $\...
Fabius Wiesner's user avatar
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 ...
Fabius Wiesner's user avatar
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 ...
Kevin's user avatar
  • 530
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
kleinbottle's user avatar
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, ...
Martin Leshko's user avatar
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$. ...
kleinbottle's user avatar
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 $...
Yevgeny Levanzov's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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. ...
Turbo's user avatar
  • 13.6k
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 ...
Or Meir's user avatar
  • 419
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+...
Fabius Wiesner's user avatar
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 ...
Fabius Wiesner's user avatar
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 ...
Matthew Kahle's user avatar
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 ...
Fabius Wiesner's user avatar
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 ...
Or Meir's user avatar
  • 419
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 ...
Victor's user avatar
  • 655
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 ...
abacaba's user avatar
  • 344
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)\} \...
Zach Hunter's user avatar
  • 3,375
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 ...
wandering_lambda's user avatar
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+\...
tota's user avatar
  • 585
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 ...
pierreciv's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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 ...
a3nm's user avatar
  • 431
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 ...
wandering_lambda's user avatar
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 ...
aleph's user avatar
  • 503
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$...
Peter K's user avatar
  • 153
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$. ...
ARQ's user avatar
  • 11
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 ...
Sudipta Roy's user avatar
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 ...
wandering_academic's user avatar
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: ...
Arun's user avatar
  • 31

1
2 3 4 5