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.

learn more… | top users | synonyms

1
vote
1answer
16 views

Numbers written into a square grid

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem: "The integers from 1 to $n^2$ are written into a ...
11
votes
4answers
1k views

N gunmen in a field

Let n be an odd integer. In some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. ...
2
votes
0answers
21 views

Turan's theorem for balanced r-partite graphs

I'm curious about the following restricted version of Turan's theorem: Among all $r$-partite graphs that are balanced (exactly $n/r$ nodes per part), what is the maximum size of a graph with no ...
0
votes
0answers
29 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...
4
votes
1answer
46 views

Maximum number of size $k$ subsets where no two overlap on more than $e$ elements.

As the title suggests: What is the maximum number of size $k$ subsets of $[1, \dots, n]$ such that no subsets overlap on more than $e$ elements? I only really care about the asymptotics, so an ...
3
votes
1answer
113 views

Lower bound for the chromatic number of $\mathbb{R}^n$

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$: $$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$ At some point in the proof we get that ...
2
votes
1answer
34 views

Combinations with maximum allowed Repetition

There are how many ways to select $r$ things from $n$ categories with maximum $k$ repetitions are allowed from each category? I think its only solvable if and only if $nk\ge r$ and I also believe ...
0
votes
0answers
10 views

To write product of 2 combinations as one combination term

Is it possible to write this product of combinarions as one comination term $\binom{N-x-1}{r} * \binom{x-1}{r} $
1
vote
1answer
28 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...
1
vote
1answer
94 views

Inclusion-Exclusion question

A careless payroll clerk is placing employees’ paychecks into pre-labeled envelopes. The envelopes are sealed before the clerk realizes he didn’t match the names on the paychecks with the names on the ...
0
votes
0answers
27 views

How to find the width knowing clique number

For an interval order, clique number=chromatic number (which is the minimum number of colors you can use for each edge to be incident to vertices that are of different colors). I also read that clique ...
0
votes
0answers
6 views

Family of graphs with structural intersection (namely, no isolated vertices)

In the book Extremal Combinatorics: With Applications in Computer Science I found the following theorem: Theorem. Suppose that $\mathcal{F}$ is a family of (labeled) subgraphs of $K_n$ such that for ...
1
vote
3answers
64 views

$K_{3,3}$ an exception to Planar Graph formula

So I have learned that for a graph to be considered Planar, if it has at least 3 vertices, you can apply the following formula to test for planarity: number of edges ≤ 3(number of vertices) - 6 also ...
0
votes
1answer
26 views

Element in chain and antichain

When analyzing one poset graph, can an element be both in the longest chain and the longest antichain? (or do chains and antichains have to be mutually exclusive?)
0
votes
1answer
67 views

Anna and Carlos are discussing a graph with 17 vertices and 129 edges

Anna and Carlos are talking about a graph with 17 vertices and 129 edges. One of them says that it must be a Hamiltonian graph, while the other say's it's not. With no other information about the ...
0
votes
1answer
66 views

Chromatic Number of Trees

All trees with more than one vertex have the same chromatic number. What is it & Why? (Is this chromatic number by any chance 2, by definition of what a tree is? Since a tree is acyclic and ...
0
votes
2answers
86 views

Pigeonhole Principle : $mn+1$ pigeons into $n$ holes.

If you have to put $n+1$ pigeons into $n$ holes, according to Pigeonhole principle, you will have to put two pigeons into the same hole. But what if you have to put $mn+1$ pigeons into $n$ holes? ...
3
votes
0answers
17 views

How should $k$ items be selected in $m$ trials so that the average size of the intersection of selected items is as small as possible?

Let $n$ be size of set of items and in $m$ trials $k$ items are selected from the set without replacement. In two different trials the same items can be selected. How should items be selected so that ...
3
votes
1answer
26 views

Cross intersecting families bound

I have been looking at the following problem Suppose $k,l \geq 1$, $k+l \leq n$ and consider $$\mathcal{A} \subseteq \binom {[n]} l, \mathcal{B} \subseteq \binom {[n]} k$$ Which are cross ...
0
votes
1answer
39 views

Rank notion of a matrix

$\newcommand{\rank}{\operatorname{rank}}$Divide $p-1$ ($p=q^k>2$ with $k>1$, $q$ prime) elements in $\Bbb F_p^\times$ into equal disjoint subsets $S_+,S_-$. Given square $0-1$ matrix $A$, ...
4
votes
4answers
61 views

Integer solutions to this problem

So I have this question, and I know that I need to start off with downgrading $782$ to $762$ (to account for $x_4$ and $x_5$ being equal to $10$). $x_1 +x_2+x_3+x_4+x_5 ≤ 782$ where $x_1,x_2 > ...
2
votes
3answers
58 views

Integer solutions of the following question:

How many integer solutions are there in this equation: $$x_1 + x_2 + x_3 + x_4 + x_5 = 63, \quad x_i \ge 0, \quad x_2 ≥10$$ I got $C(56,3)$. Is that correct?
3
votes
2answers
66 views

How to obtain $n$ maximally different binary vectors with equal number of zeros and ones?

Imagine the set of all binary vectors of length $2m$ where each of the vectors has $m$ ones and $m$ zeros. I want to select some $n$ of these vectors such that the shortest distance among all pairs of ...
1
vote
0answers
52 views

Question of difficult matrix problem, minimum number of times

There is a $n$×$n$ matrix $A_n$. All entries are $0$ at first. $\left( \begin{array}{ccc} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 ...
8
votes
1answer
97 views

Minimum number of circles with 3 neighbors

It is possible to arrange congruent circles on the plane in such a way that no two circles overlap and each circle adjoins exactly three other circles. The picture shows an example with 16 circles. ...
1
vote
1answer
33 views

Union of each family is not the whole set

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least ...
10
votes
1answer
126 views

No sum of three numbers equals another number in set

Consider the set $S=\{1,2,\ldots,1000\}$. What is the maximum size of a subset $S'$ such that for any distinct $a,b,c,d\in S'$, we have $a+b+c\neq d$? We can choose $S'=\{333,334,335,\ldots,1000\}$, ...
11
votes
2answers
113 views

Students who see ears of another student

A student is standing in each cell of an $n\times n$ grid, looking at one of the four directions: up, down, left, right. It turns out that no student is at the border and looking out of the grid, and ...
0
votes
0answers
39 views

Product of two combination terms

Is it possible to write the product of these two combinations as one combination term $N\choose r$$M\choose r$ where $r<N,M.$ Is it possible to say anything about the kind of distribution it ...
8
votes
3answers
364 views

Chips do not form rectangle on board

Given is an $n\times n$ board with $n\geq 3$. We place a chip in some cells, so that no four chips form a rectangle with sides parallel to the sides of the board. How many chips can we place, at most? ...
1
vote
0answers
40 views

Intersection theorems for a certain type of subsets of integers modulo $N$

I've been working on something with integers modulo $N$ and have sort of hit a roadblock where I'd like to have some references. The particular problem goes as follows. We have a system $\mathcal{S}$ ...
0
votes
1answer
29 views

Tiling a rectangle with $n$ rectangles to maximize product of areas

Consider a rectangle $R$ with integer width and integer height. We want to tile $R$ using exactly $n$ rectangles with integer dimensions. Now we carefully want to choose such rectangles so that ...
5
votes
2answers
59 views

Largest subset with no pair summing to power of two

For positive integer $n$, define the set $A_n=\{0,1,\ldots,n\}$. What is the size of the largest subset of $A_n$ such that the sum of any two (not necessarily distinct) elements in it is not a power ...
2
votes
2answers
53 views

Bounds on number of nice subsets

There are $2n$ people. Some subsets of people are called nice; the empty subset is nice. For any nice subset $A$ with $i<n$ people, there are at least $2(n-i)$ people $x\not\in A$ such that ...
2
votes
1answer
54 views

Placing non-attacking $2\times 2$ squares

Given a $1000\times 1000$ board. We can place non-overlapping $2\times 2$ squares on the cells. Two $2\times 2$ squares are said to attack each other if they lie in the same pair of adjacent rows (or ...
4
votes
1answer
57 views

Maximum number of squares with same number

Given a $1000\times 1000$ board. At the beginning, all cells have $0$ written on it. In an operation, we are allowed to choose any $130\times 130$ subboard and increase every number in this subboard ...
9
votes
1answer
140 views

Collection of subsets with adding one element property

Let $\mathcal{F}$ be a collection of subsets of $\{1,2,\ldots,n\}$ such that for any set $A\in\mathcal{F}$, there exists $B\not\in \mathcal{F}$ such that $A\subset B\subseteq\{1,2,\ldots,n\}$ and ...
10
votes
3answers
106 views

Every $3\times 3$ square has even number of painted cells

Given a $1000\times 1000$ board. We paint some cells (at least one) so that in every $3\times 3$ square, an even number of cells are painted. What is the minimum number of painted cells? One way to ...
5
votes
3answers
114 views

Least possible number of squares with odd side length

An $n\times(n+3)$ rectangular grid ($n>10$) is cut into some squares, with all cuts being along the grid lines. What is the least possible number of squares with odd side length? [Source: Russian ...
5
votes
1answer
53 views

Selecting cells so that every $2\times 2$ square is odd, then even

Jacob selects some cells from a $12\times9$ table, so that every $2\times 2$ subsquare contains an odd number of selected cells. He then selects some more cells, so that every $2\times 2$ subsquare ...
2
votes
1answer
106 views

Extremal set theory problem

What are good bounds(asymptotic bounds preferred) on the cardinality of the largest family $S$, of $m$-element subsets of an $n$-element set, if any pair of elements intersect in a set that has ...
5
votes
2answers
68 views

Choosing subsets to cover larger sets

I think this is probably known/easy, but I can't solve it. Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of ...
0
votes
1answer
34 views

Extremal Finite Set Book Recommendation

I want to read Extremal Finite Set Combinatorics in some detail. (By 'Extremal Finite Set Combinatorics' I mean the subject which covers theorems like Sperner's Theorem, Erdos-Ko-Rado Theorem, ...
6
votes
2answers
230 views

A method of making a graph bipartite

If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite? ...
0
votes
0answers
62 views

Sperner family intersection with chains.

Consider a maximal sperner family $F$ of subsets of $X = \{ 1,2,3 \ldots n \}$. I need to prove that this family intersects with each chain of subsets exactly once. Each chain is defined as : ...
0
votes
0answers
44 views

K- Regular families. Proof of existence.

A family F of subsets is regular if every point lies in a constant number r of the elements of F. Theorem : Let $b,k,n,r$ be positive integer satisfying $bk = nr, k<n, b\leq $ $n\choose{k} $. Then ...
0
votes
1answer
61 views

Proof of De Bruijn-Erdos theorem

I am reading Cameron's Combinatorics and came across following part of the proof of De Bruijn-Erdos theorem which I am unable to follow. $F$ is the family of set such that any two sets in $F$ ...
4
votes
3answers
195 views

Biggest subset of $\{1, 2 … 1000\}$ such that difference between any pair of elements $\neq 4, 7$

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V ...
8
votes
2answers
186 views

A Sperner type problem on infinite antichains

Let $\mathcal{A} \subset 2^{\mathbb{N}}$ be an antichain (with respect to containment). I want to measure the size of $\mathcal{A}$ in the following way: I create a set, $S$, by flipping a fair coin ...
2
votes
2answers
60 views

Graph containing every trees of size $n$ as subgraphs

What is the minimum number of edges of graph $G$, so that every tree of size $n$ is a subgraph of $G$? I personally managed to find a lower bound of $c n \log n $ and an upper bound of $C n \log ...