Mathematics Stack Exchange
Mathematics Stack Exchange

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.

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.

Examples include maximum cliques or independent sets in graphs, the largest possible family of subsets of a given set such that any two of them intersect, the minimum size of a set of lotto bets guaranteeing winning a price in a certain category, etc.

758 questions
6
votes
3 answers

Show that if there are 101 people of different heights standing in a line

Show that if there are 101 people of different heights standing in a line, it is possible to find 11 people in the order they are standing in the line with heights that are either increasing or decreasing.
aaaashasha
  • 243
  • 3
  • 6
  • 12
4
votes
0 answers

Ramsey Theory Problem

Let $C(s)$ be the smallest $n$ such that every connected graph on $n$ vertices has, as an induced subgraph either a complete graph $K_{s}$, a star $K(1,s)$ or a path $P_{s}$ of length $s$. Show that $C(s)\leq R(s)^{s}$, where $R(s)$, is the s…
user62877
  • 41
3
votes
1 answer

Suppose there are k points, no 3 of which are collinear. What is the upper bound on the number of quadrilaterals we can form?

We understand that the number of triangles possible is given by kC3, since any selection of 3 points uniquely determine a triangle. This is not true for quadrilaterals though, since for selections where 1 of the points lie within the other 3, we can…
hoogepooge
  • 31
3
votes
0 answers

Size of collection of $k$-element subsets of $n$-element set whose pairwise intersections are at most 2.

I am trying to determine the maximum possible size of a collection of $k$-element subsets of {$1, 2, \cdots n$} set whose pairwise intersections are at most 2. It's clear that when $k = 3$, its just the number of distinct three element subsets of…
Yunus Syed
  • 1,737
2
votes
1 answer

Maximal rectangle in a permutation

Suppose you have a permutation of n elements, and it is represented by colouring squares in a n by n grid of squares, where only one square is coloured in each row or column. Find the minimum area of the largest rectangle in the grid that does not…
tehjh
  • 384
2
votes
1 answer

Find maximum size of set family, where at least one member has at least one of any three points, but do not contains all those three points

Let $n$ and $s$ be non-negative integers such that $n\geq 3$ and $2s\log2>3\log n$. Prove that there exists sets $A_1,A_2,\ldots,A_s \subseteq [n]$ such that for every $B\in \binom {[n]} 3$ there exists $1 \leq j \leq s$ with both $A_j \cap B \neq…
Hai Phan
  • 743
  • 5
  • 12
2
votes
1 answer

Maximum size of k-uniform set family that satisfies a condition

Let $n \leq 2k$ and $A_1,A_2,...,A_m \subseteq [n]$ be distinct $k$-uniform set where $A_i\cup A_j \neq [n]$ for all $1 \leq i < j \leq m $. Prove that $$m \leq (1- \frac{k}{n}) \binom n k$$ and that equality can hold. I don't know if it is…
Hai Phan
  • 743
  • 5
  • 12
1
vote
0 answers

Maximal size of familes of subsets with no union.

I'm looking for the answer of following problem: Find the maximal size of $S\subseteq 2^{[n]}$ such that there are no distinct $A,B,C\in S$ such that $A\cup B\not = C$. A possible construction is all set of odd size, which $\#S=2^{n-1}$. A possible…
Peter Wu
  • 817
  • 5
  • 15
1
vote
1 answer

The union basis of a group of finite sets

Given a finite group of finite sets $\mathcal{A}$, how to find a smallest group of finite sets $\mathcal{B}$, such that for any finite set $A\in\mathcal{A}$, $A$ can be expressed by the union of some finite sets…
ljw
  • 21
  • 3
1
vote
0 answers

Bollobás Modern Graph Theory upper bound for Zarankiewicz problem

On page 112 of Bollobás' book Modern Graph Theory, Lemma 9's conclusion includes the following inequality: I understand the proof of this lemma up to the following inequality: But then the last sentence of the proof seems to imply that the left…
Peter
  • 63
1
vote
2 answers

The largest sum of products of pairs of number's terms

Someone, please, make that title more readable. My lack of math English does not let me. Given $A = a_1 + ... + a_k;\ A, a_i > 0$ what is $\max\left(\sum_{i
Alex
  • 137
  • 5
1
vote
0 answers

Maximum intersection of k-neighborhoods of a family of n-subsets

Given a family $\mathcal{F}$ of distinct $(n-1)$-subsets of a ground set $S$ on $N$ elements (where $N > 2n$), what is the maximum cardinality of a family $\mathcal{F}'$ of $n$-subsets of $S$, such that $|A \cap B| \geq k$ (where $1 \leq k \leq…
abhishan82
  • 11
1
vote
0 answers

Optimizing a network of multi-pole switches

I am working on designing an electrical network of multi-pole switches. Because of this, it should be possible to use the multiple poles to reduce the number of microcontroller pins that must be used, but I am having trouble figuring out how to…
AJMansfield
  • 1,025
0
votes
1 answer

Shadow of a set system

I'm currently learning something about Sperner's Lemma and then the LYM Inequality. In trying to prove the LYM Inequality, the proof uses the concept of a shadow but I can't seem to get a proper grip of what it actually means. I've tried 'drawing it…
Haikal Yeo
  • 2,224
0
votes
1 answer

Get the extreme value with equation of line passing through point

I didn't have any idea about the question. First, I asked ChatboxGPT and got the hint, then wrote the below solution for (5-1). \begin{array}{l} \because q=Ap+B\Longrightarrow B=q-Ap\\ \therefore A^{2} +B^{2} =A^{2} +( q-Ap)^{2} =A^{2} +q^{2}…
rann rann
  • 125
1
2