Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
2answers
28 views

For any permutation $\sigma$ of $\{ 1, \dots ,n \}$ there exists $k$ such that $|k- \sigma (k)| \le \frac{n}{2}$

Let $n \ge 2$ be an even number. Is the following true? For any permutation $\sigma$ of $\{ 1, \dots ,n \}$ there exists $k$ such that $$|k- \sigma (k)| \le \frac{n}{2}$$ and is $n/2$ optimal? I ...
0
votes
0answers
11 views

Lower bound of number of independent sets

Let $G$ be a connected regular graph with even number of vertices $v$. Also let $i_{v/2}(G)$ be the number of independent sets of $G$ of size $\frac{v}{2}$. Is it possible that $i_{v/2}(G)> 2^{v/2}$...
0
votes
0answers
15 views

Distribution in the combinatorial optimization

There is a set A containing $N$ elements. Then we randomly choose $M$ out of $N (N≥M)$ elements to form a subset B and get the objective function $f(B)$. Different $B$ may lead to different $f(B)$. ...
0
votes
1answer
20 views

Distribution of the knapsack problem

I am considering a special knapsack problem. The knapsack capacity is $M$. There are $N$ items ($N≥M$). The weight of each item is $1$. The profit for each item $i$ is $p(i) ≥ 0$. Thus, $M$ items can ...
6
votes
1answer
114 views

Minimal number of questions to identify a subset

This is a curiosity question. Recently I stumbled across the following problem : Given three integers $k,m, n$ such that $m+k\leq n$. A friend chooses a subset $S\subseteq\lbrace1,\ldots,N\rbrace$...
3
votes
1answer
35 views

If $G$ is any n-vertex triangle free graph not containing a copy of $D_d$, then $e(G) \leq n(d-1)$

when revising for an upcoming exam on Graph Theory I came across the problem above. This was the last part to a question on Extremal Graph Theory, and in the previous parts, the question covered the ...
0
votes
0answers
28 views

Minimum number of binary integer variables to handle $AND$ and $OR$ implications in Mixed Integer Linear Programming?

Suppose I want to have an integer program for handling the cases $(x_1>1)\wedge(x_2>1)\wedge(x_3>1)\wedge\dots\wedge(x_n>1)\implies\delta=1$ $(x_1>1)\vee(x_2>1)\vee(x_3>1)\vee\...
4
votes
0answers
46 views

Does there always exist a Chebyshev center of three constant weight points in $\mathbb F_2^n$ which is equidistant?

Given three distinct points $x_1,x_2,x_3$ in $\mathbb F_2^n$ (endowed with the Hamming metric $d(\cdot,\cdot)$) with the same (but arbitrary) Hamming weight, the Chebyshev radius of them is defined as ...
0
votes
0answers
16 views

Turan density results for 4- or 5- graphs

I was wondering if there are results for Turan densities of 4- or 5-graphs (hypergraphs). I am aware of several surveys of hypergraph Turan densities (due to Pikhurko, Keevash), but these mainly focus ...
0
votes
1answer
26 views

Allocating balls among boxes under specified conditions

There are $k$ boxes to which a subset of $nk$ balls are to be allocated. The full set of $nk$ balls consists of $k$ balls numbered $1$, $k$ balls numbered $2$, ... , $k$ balls numbered $n$. Each box ...
4
votes
0answers
62 views

Small & Balanced family of sets

I have the following problem: Let $\epsilon >0$, and $[n] = \{ 1,2,...,n\}$ the set of positive integers up to $n$. There exists a family of subsets $\mathcal{F} \subseteq 2^{[n]}$, such that ...
2
votes
2answers
92 views

Arrange the numbers in the given rectangular blocks

Consider the set $\{ (1,1), (1,2), \cdots , (1,10), (2,1), (2,2), \cdots , (10,10)\}$. The set contains all possible pairs (ordered) of numbers involving integers from $1$ to $10$. There are $100$ ...
10
votes
3answers
193 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
72 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
32 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
41 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 ...
-1
votes
1answer
189 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
142 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
39 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 ...
0
votes
1answer
82 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
88 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
78 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
88 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
253 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
46 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
30 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
12 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
53 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
33 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
104 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
42 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
52 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
44 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
69 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
47 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
1answer
392 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
28 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
21 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
50 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
39 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
142 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
30 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
37 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
47 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
628 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
122 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. ...