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.

3
votes
2answers
36 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
31 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 ...
5
votes
2answers
95 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
35 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
0answers
18 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
37 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
66 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
43 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 ...
11
votes
0answers
297 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
23 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
19 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
40 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
31 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 ...
13
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
96 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
33 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
39 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 ...
14
votes
0answers
588 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
84 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
55 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
21 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
26 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
50 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
43 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$?
2
votes
1answer
31 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
41 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
44 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
64 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 ...
0
votes
1answer
22 views

Minimum boundary size in grid

In an infinite 2-D grid, $n^2$ cells are painted. What is the minimum number of unpainted cells that share a side with at least one painted cell? The answer should be $4n$, occurring when the $n^2$ ...
3
votes
2answers
851 views

Smallest $r$ for which there is an $r$-coloring of the grid wherein no two colors are adjacent more than once.

Consider ways of coloring the $n \times n$ grid with $r$ labels so that no two labels are adjacent (horizontally or vertically) in more than one place. Is there a good upper or lower bound on the ...
0
votes
0answers
22 views

Extremal combinatorics problem on graph matching

Let $A$ and $B$ be two disjoint set of vertices. Let $\{M_i\}_1^n$ be $n$ edge-disjoint matchings from $A$ to $B$. Let $G$ be the graph with $V = A \cup B$ and $E = \cup_{i} M_i$. Assume that for ...
1
vote
2answers
35 views

Upper bound on cumulative power of system of limitedly intersecting subsets?

We have a set $S$ of power $n$ and $k < n$ subsets $S_1, \ldots, S_k \subseteq S$ such that $|S_i \cap S_j| \le 1$ when $i \ne j$. Is there any nontrivial upper bound on total power of sets $S_1, \...
17
votes
1answer
1k views

Number of steps the path-avoiding snail must take before a step size of $(2n - 1)/2^k$?

Suppose the path-avoiding snail walks along the grid according to the following algorithm: At each step, the snail steps unit distance if doing so will not collide with its trail. If a step of unit ...
1
vote
2answers
31 views

Given a graph with n vertices, if it have more than $\frac{nt}{2}$ edges then there exists a simple path of length $t+1$.

I have been working on this problem for a while, and yet I do not have a clear lead. Currently all I have is that the average degree is greater than $t$ so exists a vertex with degree at least $t+1$, ...
-2
votes
1answer
34 views

Combinations help please [closed]

What is the total combination I will have if I have 13 children and each kid has a choice to choose one of these 3 fruits a pears, grapes and orange(of which i have unlimited supply of each fruit)........
3
votes
1answer
53 views

Problem 2.2 from Jukna's “Extremal Combinatorics”

This is problem 2.2 from Junka's Extremal Combinatorics. The problem is as follows: Let $A=(a_{ij})$ be an $n \times n$ matrix with $n \geq 4$. The matrix is filled with integers, and each integer ...
0
votes
1answer
30 views

Trying to compute a limit for the Turán number

I have been trying to figure out how to compute the limit shown below. Let me replace $p-1$ with $k$ to make things easier. If $v$ is a multiple of $k$, that is, $v=qk$ for some integer $q$, then ...
3
votes
0answers
109 views

A Combinatorial Geometry Problem With A Solution Using Extremal Principle

I have solved this following Combinatorial Geometry Problem using extremal principle.Please check whether this solution is correct or not.Also write if you have any other solution. Problem :- Let $...
0
votes
0answers
48 views

Given N sets of partitions, find a partition such that it satisfies a criterion

Given a collection of partitions $P_i$ of a set $X$, find a partition $P$ such that each one of the sets in this partition is subset or equal to at most one set in each of $P_i$, i.e., for $P_1$ = $\{...
1
vote
0answers
50 views

Extreme Heilbronn — Maximal count of smallest triangle?

For the Heilbronn problem, here's an extreme case I found with 300 triangles having the smallest area, on 84 points. Can anyone find a position with a higher repetition in the smallest triangle area? ...
1
vote
1answer
66 views

Count number of subsets of 3 elements either disjoint or whose intersection is a singleton

Suppose we have a set of $n$ elements. We want to know the maximum number of subsets of $3$ elements we can find of this set such that no two subsets have an intersection with $2$ or more elements. ...
0
votes
1answer
42 views

Is this a valid counterexample for this inequality concerning the growth functions of set families?

Here is what I am trying to prove: Let $A$ and $B$ be two set families, then $G(A \bigcup B,m)\le G(A,m)G(B,m)$ where $G$ is the growth function. I think the above result holds iff both $G(A,m)$ ...
1
vote
1answer
32 views

question about $k$-stable classes of graphs

I do not think I am understanding the definition above. If I start out with a graph $G$ and two non-adjacent vertices $x$ and $y$ then to obtain $G^*$ I keep adding edges to $G$. I have tried looking ...
6
votes
3answers
148 views

Best way to fill a $8\times 8$ board

You have an $8\times 8$ Battleships board and need to place battleships of sizes $1\times 1$, $1\times 2$, $1\times 3$, $1\times 4$, $1\times 5$ on the board to cover as much of the board as possible. ...