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

0
votes
0answers
12 views

Unique combinations of 5-digit alpha code, 23 alpha digits

I'm using a 5-digit alpha code consisting of 23 alpha characters for each digit. What is the number of unique combinations?
0
votes
0answers
11 views

Meaningful Extreme value distribution

Extreme value theory (EVT) dictates that the limit distribution of the minimum of the set of i.i.d. Chi-square random varibales $\{C_1,C_2,\cdots,C_n\}$ is Weibull. The Weibull distribution has ...
14
votes
1answer
178 views
+100

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n ...
3
votes
1answer
32 views

Equality of unions of subsets of finite set

For $n \in \mathbb{N}$, let $\alpha_n$ be the biggest number such that there exist $\alpha_n$ subsets $M_1, \dots, M_{\alpha_n} \subseteq \{1, \dots, n\}$ with the property \begin{equation*} M_{i_1} ...
0
votes
0answers
11 views

Is this a Combinatorial Optimization problem with Multiple Constraint Satisfaction?

Given n-dimensional data consisting of over 20000 samples with 200 dimensions, using this as an example: ...
3
votes
1answer
50 views

Dependency of submatrix used in a combinatorial strategy .

This is a verification post , Please inform if anything is undefined or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment. Introduction: Given a matrix A ...
1
vote
1answer
20 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
22 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
51 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
39 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
11 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
28 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
7 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
29 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
71 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
87 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
59 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
71 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
57 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
98 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
45 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
30 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
54 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
141 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
118 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
110 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
71 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
35 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
232 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? ...