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

775 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
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, ...
• 51
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$...
• 1,773
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-...
• 19
1 vote
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}$ ...
• 5,182
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 ...
188 views

• 2,103
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 ...
• 378
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
• 378
88 views

• 5,215
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 ...
• 311
44 views

• 41
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 ...
• 1,186
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 (...
• 1,472
1 vote
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$ ...
• 31
1 vote
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 ...
• 1,773
1 vote
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 ...
• 21
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 ...
1 vote
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$ ...
• 2,454
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 ...
• 51
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$ ...
• 1,098
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 ...
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 ...
• 2,474
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 |\mathcal{A}|\le{n\choose{n/2}}+{n\choose{n/2-1}}.\end{...
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 ...
• 2,733
1 vote
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 ...
• 151
1 vote
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 ...
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-...
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 ...
1 vote
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 $$\sum_{i=0}^n\frac{|\mathcal{F}_i|}{{n\choose i}}\leq k,$$...
1 vote
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 ...
• 2,103
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 ...
• 2,103
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)$ ...
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\}$. ...
• 2,103
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$ ...
• 3,623