Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

8
votes
2answers
76 views

We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work.

We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work. Suppose we don't know which batteries are charged and which ones are uncharged. Find the least ...
1
vote
1answer
68 views

$A_1,A_2,…,A_k\subseteq \{1,2,…,11\}$ are such that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$?

Say $A_1,A_2,...,A_k\subseteq \{1,2,...,11\}$ are such a distinct sets that for any three of them at least two are not comparable by inclusion. What is a maximum of $k$? I'v got idea for this problem ...
1
vote
0answers
26 views

Maximum number of triangles given fixed number of edges

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $O(E^{1.5})$ and the maximum occurs with it’s a clique. Now my ...
1
vote
1answer
14 views

Relation between maximum matching of a graph and its complement

Let $f(n)$ be smallest value such that for every graph $G$ on $n$ vertices, either $G$ or complement of $G$ contains a matching that covers $f(n)$ vertices. What's the best bound on $f(n)$? I can ...
-2
votes
1answer
85 views

Optimization problem for routes

Let a group of farms each have a p-letter name. No two farms have the same name, however, and they all only consist of x's and z's. For example, if p=2, then xx, zz, xz, zx are the farms in the state. ...
5
votes
1answer
140 views

Sum and minimum in $3\times 3$ table

A $3\times 3$ table is filled with non-negative real numbers so that each row sums to $1$. A subset of cells is called admissible if it has size $3$ and the three cells all lie in different rows and ...
0
votes
2answers
37 views

Let $S$ be a subset of $\{1, 2, \dots , 2019\}$ such that no two members of $S$ differ by 1, 2 or 9. What is the upper bound of the size of $S$?

My solution is that you can take 4 integers from any 12 consecutive integers, and since $2019 = 168*12+3$ you'll have a total of $168*4+1 = 673$ integers in $S$. I have no way to check if my solution ...
1
vote
1answer
56 views

Let $ T= \{A \subset \{1,2,\ldots,9 \} \ ; \ |A|=5 \}$. Find $n_{\min}$ if for any $ X \subset T $, $|X|=n$ exist $A,B \in X$ so that $ |A \cap B|=4$.

Let $ S=\{1,2,\ldots,9 \}$ and $ T= \{A \subset S \ ; \ |A|=5 \}$. Find the minimum value of $n$ such that for any $ X \subset T $ with $|X|=n$ there exist two sets $A,B \in X$ so that $ |A \cap B|=...
1
vote
2answers
76 views

Maximum cardinality of a set of subsets

Let $N$ be a system of subsets of the set $X = \{1,2,3,\cdots ,n \}$ such that there are no three elements $A,B,C \in N$ such that $A \subset B \subset C$. Prove that $$|N| \leq 2 \cdot {{n}\choose{ \...
4
votes
1answer
70 views

Subsets of a set with common elements between themselves

Let $S=\{1,2,\ldots,n\}$. Let $A_i\subset S$ for $i\in\{1,2,\ldots,m\}$. Impose the following conditions $|A_i|=r$ with $r<n$ for all $i$. $|A_i\cap A_j|=t$ for all $i\neq j$, with $t<r$. Let $...
5
votes
1answer
82 views

Optimizing a winning strategy for a quick tabletop game

A friend of mine recently shared the following puzzle with me: Puzzle: A circular turntable is divided into four congruent quadrants by two perpendicular lines. (Think of a circle in the $xy$-...
8
votes
1answer
204 views

Identify a truth-teller among a group of truth-tellers and (honest) liars.

This question is inspired by this thread. In that thread, a liar may both tells lies and truths. However, in my version, liars always lie. Main Question. A group of people consists of $m$ truth-...
1
vote
2answers
43 views

A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4

If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number). I really hope the best bound is not ...
2
votes
0answers
27 views

Upper bound for certain number of colorings of $(2k,k^2)$-graph $G$

Let $G$ be a graph with $2k$ vertices and $k^2$ edges, $k\geq 1$, such that $G$ contains $K_{k-i, k+i}$ as a subgraph, where $0\leq i \leq k-1$. Suppose that the complete bipartite subgraph $K_{k-i, ...
0
votes
0answers
11 views

How can dividing the graph into k-1 subsets guarantee that a clique on k vertices is avoided ?

Could someone provide a formal proof or an intuitive sense of it ? The proof for Turan's Theorem is provided for reference
3
votes
2answers
47 views

tree has exactly $k$ nodes with degree $4$. Show that this tree has $2k+2$ leaves.

Prove: If a tree has exactly $k \geq 1 $ nodes with degree $4$, then this tree has at least $2k +2 $ leaves. ( nodes with degree $< 4 $ are only allowed for the leaves ). So I think that we can ...
1
vote
2answers
32 views

Size of largest subset $F$ of $\mathcal{p}(X)$ such that any two subsets in $F$ intersect no trivially. [closed]

Help with the following Putnam problem: let $S$ be a finite set, and suppose that a collection $\mathcal{F}$ of subsets of $S$ has the property that any two members of $\mathcal{F}$ have at least one ...
4
votes
2answers
103 views

What is the biggest possible sum $|X_1-X_2|+|X_2-X_3|+\cdots+|X_{n-1}-X_n|$ where $X_1,X_2,\cdots,X_n$ are first $n$ positive integers?

What is the biggest possible sum $|X_{1}-X_{2}|+|X_{2}-X_{3}|+\cdots+|X_{n-1}-X_{n}|$ where $X_{1},X_{2},\cdots,X_{n}$ are first $n$ positive integers?
2
votes
1answer
40 views

Bounds on $d$ for tiling $\mathbb{Z}^d$ with subset of $\mathbb{Z}^n$?

According to this remarkable paper by Gruslys, Leader and Tan, given any subset $T$ of $\mathbb{Z}^n$, $\exists d$ s.t. $T$ tiles $\mathbb{Z}^d$. This immediately became one of my favourite ...
0
votes
1answer
31 views

Question on cross-cuts contained in cross-cuts

Let $X$ be a finite set with $|X| =n $ and $\mathcal{A} \subset \mathcal{P}(X)$ a set system. Call $\mathcal{A}$ a cross-cut if $\forall B \in \mathcal{P}(X), \; \exists A \in \mathcal{A} $ such ...
1
vote
1answer
41 views

How can I get maximum number of vertices if I already know edges

If I already know edges how can I get the maximum number of vertices? Question: There is a graph that has $36$ edges, and where every vertex has degree at least $5$. What is the maximum number of ...
1
vote
1answer
67 views

How to maximize the total auction price for a set of bids subject to bidder constraints

I want to auction a set of ASSETS (A) and fetch the maximum total price. The bidding is simultaneous and works as follows. Say I have a collection of BIDDERS (B) who, individually, bid to purchase a ...
1
vote
0answers
46 views

Infinite lattices

I would like to know a bit more about infinite lattices. Can you recommend me a book that study lattices without assuming they are finite? I have found various combinatorial books talking about ...
1
vote
1answer
32 views

Maximising $K_{s}$ in a $K_m$ free graph

A graph $G$ on $n$ vertices does not contain a $K_{m}$ (complete subgraph with $m$ vertex). What is the maximum number of $K_{s}$ ($s<m$) in $G$, taken as a function of $s$, $n$, and $m$?
1
vote
1answer
28 views

finding minimum number $k$-subsets containing all pairs of elements of $[n] := \{1, 2, 3, \ldots, n\}$

Let $A_1,A_2, \dots, A_m$ be $k$-subsets (each of size $k$) of $[n] := \{1, 2, 3, \dots, n\}$ such that for every pair $i, j \, (1\le i < j \le n)$ there exists some $A_l \, (1\le l \le m)$ such ...
15
votes
0answers
343 views

Minimum number of balanced partitions

For any multiset $x_1,x_2,\ldots,x_{2n}$ of positive real numbers, a partition into two nonempty subsets $(A,B)$ is called "balanced" if $\text{sum}(A)\geq\text{sum}(B)-\max(B)$ and $\text{sum}(B)\geq\...
1
vote
1answer
38 views

k-subsets with some pair containing every element

Let $[n] := {1,2, 3, \dots, n}$ and $k$ be some fixed positive number. Whats is the smallest number $m$ so that $A_1, A_2, \dots, A_m$ are k-subsets(each of size k) of $[n]$ and for every $x \in [n]$ ...
0
votes
1answer
24 views

Intersecting r-families with any two intersects in more than s elements.

There is a well-known fact that if $F$ is a family of $r$-subsets of an $n$-set no two of which intersect in exactly $s$ elements then $\vert F \vert \leq n^{\max\{s, r-s-1\}}$. But are there any ...
0
votes
1answer
20 views

Clarification regarding Dilworth Theorem Proof

This is the proof I am talking about. http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf It is given that : P⁻∩ P⁺=A Otherwise there exists x,i, j such that ai < x < aj and ...
0
votes
1answer
46 views

Clarification about this proof about Dilworth's Theorem

Theorem 6.1. Let P be a partially ordered finite set. The minimum number m of disjoint chains which together contain all elements of P is equal to the maximum number M of elements in an antichain of P....
3
votes
0answers
33 views

Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix

I am trying to find a solution (or algorithm) for the following combinatorial problem: Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
12
votes
3answers
2k views

An invisible ghost jumping on a regular hexagon

Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i....
5
votes
1answer
132 views

Two points no matter how you choose from the six points in the unit disk are at distance at most 1?

Six points are to be chosen in a unit disk ($x^2 +y^2 \leq 1$) , such that distance between any two points is greater than 1? I am unable to, I think I want to prove formally that no matter how the ...
0
votes
0answers
29 views

The fraction of highly-increasing sequences among the set of non-decreasing sequences

The number of non-decreasing sequences in $\{0, 1, \ldots, m\}^n$ is $\binom{m + n}{n}$. Consider the following generalization of non-decreasing sequences. Set $x_0 = 0, x_{n + 1} = m$ and call $(x_1, ...
4
votes
1answer
34 views

Finding the optimal placement of weights on a circle

I'm wondering if anyone knows any efficient algorithms for finding the optimal placement of weights around a circle to minimize the center of mass. The mathematical formulation is as follows: $$\min_{...
3
votes
0answers
42 views

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 ...
15
votes
0answers
614 views

Smallest region that can contain all free $n$-ominoes.

A nine-cell region is the smallest subset of the plane that can contain all twelve free pentominoes, as illustrated below. (A free polyomino is one that can be rotated and flipped.) A twelve-cell ...
1
vote
0answers
106 views

Simpler solution for EGMO 2018 Problem 3?

This is a reformulation of problem number 3 from the 2018 European Girls Math Olympiad. It took me several days to come up with a complete solution, and I'm wondering if there is an easier way. ...
1
vote
1answer
58 views

Minimizing maximal adjacent integer sum on a circle

Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? Some nontrivial examples of $(n,k)$ are welcome. A random algorithm that ...
0
votes
0answers
60 views

Writing Profit function as part of optimization problem involving two products

A company produces two types of products $A$ and $B$. Production cost for a unit of A is USD 70, while for a unit of B it is USD 80. Demand functions for both are given as such : $qA = 160 - 2pA + ...
1
vote
1answer
27 views

On properties of extremal graphs

Let H be a graph, and define $c_n(H) := \frac{ex(n, H)}{\frac{n(n-1)}{2}}$ Prove that $c_n(H) \leq c_{n−1}(H)$, and show that $\lim_{n→∞} c_n(H)$ exists. So first of all, if we managed to show that ...
0
votes
1answer
55 views

combinatorics for valid Password with blacklist word

i have a problem with password combination , let said the min length of pass is 5 and the max is 6 required : min 1 upper, 1 lower and 1 digit i know to got all the combination of the passoword : (...
0
votes
0answers
50 views

Bound on conditional expectation and conditional probability

Let $\epsilon_i, \, i=1, \ldots, N$ be random variables which are taking values on $\pm A$ with equal probability and such that $\sum_{i=1}^N\epsilon_i=K$. Let $N=2n=\sum_{i=1}^{2n}n_i, \, n_i \in \{0,...
2
votes
1answer
46 views

Groups whose minimal number of generators is $\log_2(|G|)$

It's a classical exercise to show that a finite group $G$ has a minimal number of generators $\leq \log_2(|G|)$. Clearly this bound is attained for $(\mathbb{Z}/2\mathbb{Z})^k$ ($k\geq 0$). ...
3
votes
1answer
63 views

Polyominoes with the most reflex exterior angles

What is the polyomino with the largest number $n$ of reflex (i.e., $270^\circ$) exterior angles that can fit in a $L \times L$ grid? How does $n$ scale with $L$?
14
votes
1answer
252 views

A conference uses $4$ main languages. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.

A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know. Source: ...
2
votes
1answer
48 views

Extremal set theory on Sperner like systems.

Consider the family of subsets $F$ of an $n$-element base set H, having the following property: For each $S\in F$ the size $|S|$ is a prime number and if $S_1,S_2\in F$ and $S_1 \neq S_2$, the $|S_1 \...
0
votes
1answer
44 views

What is the number of ways in which a fence can be colored if it consists of 45 pickets and there are 5 colors?

You are to paint a fence consisting of 45 fence pickets, and have 5 colors to choose from. Each picket is to be colored in precisely one color, but different pickets can be of different colors. In ...
0
votes
0answers
45 views

How many people do we need for seemingly random meet up of each other?

This is just out of curiosity. Let's say there is a group of people, $A$, that never met each other before. The size of $A$ is $|A|=N$. In $A$, there are people, $a_i$, where $1 \leq i \leq N$. Now, ...
3
votes
1answer
73 views

Coloring the edges of a complete graph such that no two edges of the same color cross

Need to color the edges of $K_n$ such that no two edges of the same color cross. Show that at least $\frac{n}{6}$ colors are needed. Show that this is doable with at most $\frac{n}{2}$ colors. Any ...