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
1answer
33 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$, ...
3
votes
4answers
54 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
53 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
51 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
38 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
85 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
28 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
122 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
106 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
28 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
359 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
34 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
0answers
15 views

At least two elements not in $A_x\cup A_y\cup A_z\cup A_w$

The number of subsets of $T=\{1,2,\ldots,n\}$ is $2^n$. Suppose we pick some of them, $A_1,A_2,\ldots,A_k$, such that for any $x<y<z<w$, at least two elements of $T$ are not in $A_x\cup ...
0
votes
1answer
24 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
53 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
51 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
51 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
53 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
132 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
100 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
100 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
52 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
99 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
61 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
27 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
215 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
43 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
38 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
56 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
183 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
178 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
57 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 ...
1
vote
1answer
116 views

total number of combinations?

Patient Age ---> Avg Visits / Year <1 year ---> 7.5 1-4 years ---> 3.0 5-14 years ---> 1.8 15-24 years ---> 1.7 25-44 years ...
0
votes
1answer
41 views

How do I find the critical values to find the maximum of this function?

The total daily profit in dollars realized by the TKK Corporation in the manufacture and sale of x dozen recordable DVDs is given by the total profit function below. $$P(x) = −0.000001x^3 + 0.001x^2 + ...
1
vote
0answers
41 views

resilience of graphs question

The following is a definition of the resilience of a graph w.r.t to a property $\mathcal{P}$ (Local resilience) A property $\mathcal{P}$ is said to be monotone if the property is preserved under ...
8
votes
2answers
195 views

Tricky (extremal?) combinatorics problem

Apologies for being unsure the best way to express this problem. I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit ...
1
vote
1answer
60 views

maximum size of a $k$-intersecting antichain of $[n]$

What is the maximum size of an antichain of $[n]:=\{1,2,3,\dots,n\}$ (say $\mathcal{A}$) such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? By antichain, I mean ...
2
votes
2answers
158 views

maximum size of a $k$-intersecting family of $[n]$

What is the maximum size of a family of subsets of $[n]:=\{1,2,3,\dots,n\}$ say $\mathcal{A}$ such that $\mid A\cap B\mid \ge k$ where $A,B\in \mathcal{A}$ and $1\le k\le n-1$? This not ...
1
vote
0answers
24 views

Szemeredi Trotter and additive combinatorics on A+AA

I am trying to get a lower bound on $|A+AA|$ where $A$ is a set, and $A+AA=\{a+bc: a,b,c \in A\}$ using Szemeredi Trotter. I would think we need to form lines of the form $y=ax+b$ where $a,b \in A$, ...
4
votes
1answer
174 views

Application of Erdős–Ko–Rado

Here is an interesting question. I believe you have to use the fact the Erdős–Ko–Rado Theorem tells you $A$ and $B$ are not intersecting, but I am unable to show it: Let $A,B \subset[n]^{(r)}$, ...
2
votes
1answer
92 views

Generalization of Erdős-Ko-Rado where intersections have cardinality in given set

Problem: Let $T\subseteq \{0,\ldots, k-1\}$ and let $\mathcal F\subseteq [n]^{(k)}$ (subsets of size $k$) such that $|A\cap B|\in T$ for $A,B\in \mathcal F$, $A\ne B$. Show that if $n\ge ...
10
votes
1answer
144 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
3
votes
1answer
118 views

Number of edges in graphs having two disjoint cycles of equal length

The question is motivated by this and this two problems. The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the ...
2
votes
3answers
287 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
2
votes
0answers
33 views

Covering the square with “crosses”.

The problem concerns covering the unit square with translates of a specific figure, which I will refer to as a "cross", using as few translates as possible. The difficulty seems to result from the ...
2
votes
1answer
42 views

Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are ...
1
vote
0answers
73 views

zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf On page 2 they give an explicit formula for the lower bound of the size of the graph. Summary: We ...
2
votes
0answers
31 views

Threshold function of the property Sperner set

Someone can to help me in the following problem about the threshold function of the property Sperner set? I don't know where to start. Let $\mathcal{F} \subseteq \mathcal{P}([n])$ be a random ...
5
votes
3answers
787 views

Show that if there are 101 people of different heights standing in a line

Show that if there are 101 people of different heights standing in a line, it is possible to find 11 people in the order they are standing in the line with heights that are either increasing or ...
2
votes
1answer
139 views

Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $ |f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...