Skip to main content

Questions tagged [extremal-combinatorics]

This tag is for questions asking for combinatorial structures of maximum or minimum possible size under some constraints. Typical questions ask for bounds or the exact value of the extremal size, or for the structure of extremal configurations.

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 views

Help on Alon and Spencer problem on probability of $\epsilon$-regularity in a random graph

Problem (Alon and Spencer, 17.6.1): Show that for every fixed $\varepsilon > 0$ and $0 < p < 1$ there is an $m_0 = m_0(\varepsilon, p)$ so that for every $n > 2m > m_0$, the ...
Saksham Sethi's user avatar
1 vote
1 answer
23 views

A couple questions about triangle-freeness using Szemeredi's Regularity Lemma

In The Probabilistic Method by Alon and Spencer, after Szemeredi's Regularity Lemma is introduced, its application on triangle-free graphs is shown with a lemma. In the proof below, however, I have a ...
Saksham Sethi's user avatar
9 votes
0 answers
138 views
+50

How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element?

Question: How many permutations of n elements exist, such that for each pair of permutations, they are still distinct after removing any element? To elaborate on what I mean by removing any element, ...
Cid's user avatar
  • 51
2 votes
0 answers
61 views

A conjecture on diagonal Ramsey numbers

Let $R(n,n)$ denote the $n$-th diagonal Ramsey number, i. e. the smallest integer $m$ such that any $m$-vertex graph contains either an $n$-clique or an $n$-independent set. Let us define a maximal $n$...
Bertrand Haskell's user avatar
0 votes
0 answers
34 views

Davenport Constant of Symmetric Group S5

I am working on computing the Davenport constant $D(G)$ of symmetric groups, which is the minimal number d such that every sequence of d elements, possibly with repetitions, of a fixed group is one-...
Mikel's user avatar
  • 19
1 vote
1 answer
55 views

Proof of variant Sperner's Theorem for divisibility posets

I'm trying to determine the size of the maximal antichain in the poset of divisors of $N$ where the partial order is divisibility. Looking at the prime factorization of $N=p_1^{e_1}\cdots p_d^{e_d}$ ...
Alan Abraham's user avatar
  • 5,182
25 votes
2 answers
1k views

What is the minimum number of avoids to never have a match in Dota 2?

In Dota2, players can avoid other players so that they will never be in the same team again. Every match is five players against five players and must have 10 players in total. Let's assume that all ...
Vinicius Morais's user avatar
9 votes
1 answer
188 views

The density of the biggest integer set without given difference

Given fixed positive integers $a_1<a_2<a_3<...<a_k$. For every $n\in\mathbb{N}$, define $S_n$ as the biggest set $S\subseteq\{1,2,3,\cdots,n\}$ which satisfies that for all $x,y\in S$ and $...
cxy_MO's user avatar
  • 156
3 votes
0 answers
316 views

A "difficult" example for the union-closed sets conjecture

This question was originally posted at mathoverflow. There is no answer there, however I want to give it a try here in case somebody has some interesting hint. Consider a union-closed family $\mathcal{...
Fabius Wiesner's user avatar
2 votes
0 answers
75 views

Smallest number of groups

Eighty-four developers sign up to contribute to a public open-source project. You need to divide the developers into $n$ subteams such that each contributor is on exactly one team. Their personalities ...
Harsh's user avatar
  • 378
0 votes
1 answer
84 views

Largest collections of subsets [closed]

I need to find largest collection of subsets of $\{1,\ldots, 84\}$ such that each subset has size 5 and any two distinct subsets have exactly one element in common. Any help is appreciated, Thanks
Harsh's user avatar
  • 378
5 votes
0 answers
88 views

Largest collection of subsets of [1,n] such that any union of two subsets is unique

Let $S$ be the set of integers from 1 to $n$. Then there are $2^n$ subsets of $S$. My question is what is the size of the largest collection, $F$, of these subsets such that the union of any distinct $...
SFA's user avatar
  • 167
4 votes
2 answers
61 views

Families of $4$-subsets with small intersection

Consider this MSE question which has following setup: We have a set $X$ with cardinality $= n$ and a family $\mathcal{F}$ of $4-$subsets of $X$ such that for two distinct $A, B \in \mathcal{F}$, $|A\...
user1001001's user avatar
  • 5,215
10 votes
1 answer
251 views

Extracting a subsequence common to infinitely many sets from an uncountable collection with uniform positive upper density

Let $\{a_n\},\{b_n\}$ be strictly increasing sequence of positive integers satisfying $a_1<b_1<a_2<b_2<a_3<b_3<\ldots$ and $(b_n-a_n) \to \infty$. Define $I_n:= [a_n,b_n]$, meaning ...
confused's user avatar
  • 311
0 votes
0 answers
44 views

Maximal size of Sperner family that only contains small subsets

Let $[n]$ denotes the set $\{1,2,\cdots,n\}$ and $2^{[n]}$ its power set. A set $\mathcal{F}\subset 2^{[n]}$ of subsets of $[n]$ is called a sperner family if for any distinct elements $A,B\in\mathcal{...
Rookie's user avatar
  • 108
3 votes
0 answers
66 views

Cover the set $\{0,1,1/2,1/3,1/4,\dots\}$ with the least amount of closed intervals of length $\delta>0$.

Let $\delta>0$ and define $N(\delta)$ to be the least number of closed intervals of length $\delta$ necessary to cover the set $S:=\{0,1,1/2,1/3,\dots\}$. For example, it is clear that $N(1/2)=2$. ...
Croqueta's user avatar
  • 123
0 votes
0 answers
52 views

Four functions theorem

In the proof of the four functions theorem (see this for example), one usually makes the following assumption wlog: the functions $\alpha,\beta,\gamma,\delta$ considered vanish outside the ...
xyz's user avatar
  • 1,000
10 votes
3 answers
224 views

What is the minimal number of pieces to surround n pieces in a Go game?

Go is a game of black and white pieces on a lattice of $19\times 19$. Pieces have liberty by having empty spaces next to them and are killed if the liberty are occupied by the opponent. Pieces are ...
ZhenRanZR's user avatar
  • 399
0 votes
0 answers
17 views

maximum number of edges in a planar graph on 11 vertces with no 5 cycle [duplicate]

It can be checked systematically that the result ex$_P (n,C_5 )$ ≤ $(12n−33)/5$ holds for n ∈ {11, 12, 13} (this turns out to be not as onerous as it might at first appear!) How to compute maximum ...
user528305's user avatar
0 votes
0 answers
30 views

Find the maximum of partition number, keeping row sums and column sums zero

For an $i \times s$ ($s\geq 3,\ 3\leq i \leq B_s$) matrix $M$ with row sums and column sums to be $0$, we partition each row by grouping equal elements together, and each row has a different partition....
Random's user avatar
  • 91
0 votes
1 answer
39 views

Maximal number of independent vectors in a Boolean space

Consider the set of length $n$ Boolean vectors, with addition defined as component-wise OR, and multiplication by a boolean scalar value defined by component-wise AND with that scalar, as expected. ...
Michele's user avatar
  • 133
0 votes
1 answer
28 views

Extremal Combinatorics Problem on words

Find the maximum length $m$ of the sequence $a_1 a_2 \dots a_m$ such that (1) Each $1\le a_i\le n(\in\mathbb{N})$ (2) No $1\le i \le m-1$ such that $a_{i}=a_{i+1}$ (3) Call $(x,y)$ good if $a_i=x, a_j=...
C TI's user avatar
  • 41
2 votes
1 answer
65 views

Given an $n$-element family $\mathcal{S}$ of average size $r$, is $\sum |S_i \cap S_j|\geq n\binom{r}{2}$?

Consider a set $X$ of size $n$, and a size-$n$ family of sets $\mathcal{S}$. The sets in $\mathcal{S}$ have average size $r$, and their intersections are of size at most $k$. I'm trying to show that ...
Lt. Commander. Data's user avatar
5 votes
0 answers
103 views

Combinatorial problem about finding equidistant words

Assume I have an alphabet $\{A,B,C...\}$ with a total of $K$ symbols. For words of same length, I define the distance $d$ between them as the number of positions in which they have differing symbols (...
mavzolej's user avatar
  • 1,472
1 vote
1 answer
67 views

What is the least number of subsets that you need to separate all the 2-element subsets of a given (finite) set. [closed]

The question more formally can be written as follows, Suppose there is a set $X$ with $|X|=n$. Suppose $S\subseteq \mathcal{P}(X)$ s.t. for any two-element subset $Y\subseteq X$ there is a $Z\in S$ ...
Arun's user avatar
  • 31
1 vote
1 answer
174 views

A generalization of Turan's theorem

The Turan's theorem gives a tight upper bound of the number of edges in a $K_n$-free graph. I didn't manage to find some information about the generalization of this theorem when we're asked to ...
Bertrand Haskell's user avatar
1 vote
1 answer
77 views

How to prove that the following conclusion is true? [closed]

Consider a set $\mathcal{X}$ with $m$ numbers, and take out $a, b, c, d$ numbers respectively. The number of combinations of $a$ number taken from $\mathcal{X}$ is recorded as $C_{m}^{a}$. The number ...
Kristy's user avatar
  • 21
0 votes
2 answers
84 views

Farther and nearest points from an ellipse to the a line segment.

I really need your help in math, I've solved this problem in several ways, but I'm not getting anywhere... Given a straight line $x-3y-9=0$ and an ellipse $x^2/9 +y^2/4 = 1$, find the nearest and ...
Masha's user avatar
  • 1
1 vote
1 answer
77 views

If a graph has exponentially many maximal cliques, what can we say about how many maximal cliques each vertex belongs to?

My question is motivated by the following example: For $n \geq 1$, let $G$ be the complete $n$-partite graph on $2n$ vertices, i.e., every vertex of $G$ is connected to all others except one. Then $G$ ...
pyridoxal_trigeminus's user avatar
4 votes
2 answers
110 views

Distinguishable subsets of the 52-card blackjack deck

I need to find, for $n = 0, 1, . . . , 52$, the number of distinguishable subsets of size n. Blackjack deck has $4$ cards for each value from $1$ to $9$ and $16$ cards of value $10$, color doesn't ...
Monia's user avatar
  • 51
4 votes
0 answers
204 views

Disjoints subsets of a multilabeled set

We are given a set of elements $U$ and $n$ binary functions, i.e. $f_i: U \to \{0,1\}$. Moreover, each function maps exactly $k$ elements of $U$ to 1. The task is to create a collection of $n$ ...
cgss's user avatar
  • 1,098
6 votes
0 answers
355 views

Decrease list difference via swaps

There are four lists, each with $100$ numbers in $[0,1]$. You want to perform as few swaps between pairs of numbers as possible, so that the difference between the sums of numbers in any two lists ...
user57012's user avatar
0 votes
1 answer
59 views

proving an inequality for combinatorial sum

The following inequality comes from the literature: N. Alon, Y. Caro, On the number of subgraphs of prescribed type of planar graphs with a given number of vertices //North-Holland Mathematics ...
licheng's user avatar
  • 2,474
3 votes
1 answer
125 views

Set system containing no chain of length $3$

Let $n$ be even and let $\mathcal{A}\subset\mathcal{P}(n)$ be a set system that contains no chain of length three. Prove that \begin{equation}|\mathcal{A}|\le{n\choose{n/2}}+{n\choose{n/2-1}}.\end{...
user avatar
3 votes
1 answer
274 views

Large family of subsets with small pairwise intersections

Let $\alpha>0$ be a constant (can be sufficiently small if necessary) and $n$ be sufficiently large. What can we say about the cardinality of a family of subsets of $\{1,2,\ldots,n\}$, each of size ...
DesmondMiles's user avatar
  • 2,733
1 vote
1 answer
86 views

An upper bound on the size of antichain

Let $P$ be a collections of subsets of the set {1,2, ..., n} such that $P$ is an anti-chain and cardinality of sets in $P$ is strictly less than $k$, where $1 \leq k \leq n$? Can we get an upper bound ...
Renrael Htam's user avatar
1 vote
1 answer
56 views

Combinatorial Problem based (indirectly) on Generalized Pigeonhole Principle

I was going through my Discrete Mathematics (Discrete Mathematics and Its Applications by Kenneth Rosen) textbook when I came across this problem. Suppose that a computer science laboratory has 15 ...
Sahil Muhammed's user avatar
0 votes
1 answer
73 views

Prove the minimum size of a separating union-closed family of sets is equal to the size of its universe

That's a statement given without proof in the following paper (page 12, ch. 3.5) about Frankl's union-closed sets conjecture. It's labeled as easy to prove, but I'm struggling with it. For non-union-...
Nikita Dezhic's user avatar
0 votes
1 answer
59 views

Dividing a hyper-sphere ( of dimension $n$) into $N$ equal measure of bounded diameter

The following is stated in the Erdös-Bollobás Paper - On a Ramsey-Turán type Problem If $n$ is a sufficiently large number, then $k+1$ dimensional sphere can be divided into $n$ sets, each of equal ...
total dependent random choice's user avatar
1 vote
0 answers
52 views

Set system containing no chain with $k+1$ sets [duplicate]

Let $\mathcal{F}\subset \mathcal{P}[n]$ be a set system such that each chain in it has at most $k$ sets. Prove that \begin{equation}\sum_{i=0}^n\frac{|\mathcal{F}_i|}{{n\choose i}}\leq k,\end{equation}...
user avatar
1 vote
1 answer
73 views

Lower bound for the size of some families of subsets of $[2n+1]$ of size $n$

Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n$, $n \ge 1$. Let $\mathcal{F} \subseteq \mathcal{A}$ be a subfamily of $\mathcal{A}$ with the ...
Fabius Wiesner's user avatar
0 votes
0 answers
25 views

Lower bound related to couples of disjoint two-element sets

I have already asked this question at MathOverflow, but without answers. I want to give it a try here, maybe somebody can answer or give interesting hints. Let $\mathcal{B}$ be the family of all ...
Fabius Wiesner's user avatar
3 votes
0 answers
124 views

A generalization of the edge isoperimetry problem for the hypercube

For any $n$, and any $1 \leq k \leq 2^n$, and any $1 \leq q \leq n-1$, we want $k$ binary vectors of length $n$, organized in a matrix $M$ with $k$ rows and $n$ columns, that will minimize $p(M,q)$ ...
Jan Arne Telle's user avatar
0 votes
0 answers
58 views

Lower bound for couples of disjoint sets in some partitions of the power set

Now crossposted at Mathoverflow. Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n]) \setminus \{\emptyset\}$. ...
Fabius Wiesner's user avatar
2 votes
1 answer
111 views

Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph

$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$ For given integers $d>0$, $k>1$ ...
Matija's user avatar
  • 3,623
9 votes
1 answer
358 views

Proving $n$ subsets $A_1, ..., A_n$ of size $\geq 2$ must pairwise intersect.

Let $A_1, ..., A_n \subseteq [n]$ be $n$ subsets of $[n]$ with $|A_i|\geq 2$. Suppose further that for every $B \subseteq [n], |B|=2$, that there exists a unique $i$ with $B\subseteq A_i$. Prove that $...
AspiringMat's user avatar
  • 2,447
6 votes
1 answer
249 views

When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Now also posted to MathOverflow. Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of ...
Mohannad Shehadeh's user avatar
0 votes
0 answers
11 views

What's the $p$-th power of a $k$-uniform tight cycle?

I understand that in a graph when there's a cycle, the $p$-th power of the cycle is when all vertices at a distance of at most $p$ from each other (on the base cycle) are joined with edges. A $k$-...
kleinbottle's user avatar
8 votes
2 answers
323 views

Between us my sister and I know everything -- how many sisters do I have?

My name is Aaron. I used to think my twin brother Bernard and I were pretty smart. You see between us, we know everything. That was until we met the triplets Charlotte, Denise, and Esther. Between any ...
Daron's user avatar
  • 10.4k
11 votes
1 answer
269 views

Maximal non-decreasing subsequence

Let $n\in \mathbb{N}$. A sequence $(y_i)$ with $0\le i\le 2^n-1$ is called beautiful of rank $n$ if for all $0\le i\le 2^n-1$, $0\le y_i\le i$. For a beautiful sequence $(y_i)$ of rank $n$ let $A((...
ZNatox's user avatar
  • 229

1
2 3 4 5
16