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
26 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
121 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
103 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
24 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
356 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? ...
0
votes
0answers
30 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
18 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
51 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
49 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
49 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
52 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
130 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
98 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
97 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
51 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
97 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
59 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
26 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
211 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
40 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
51 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
182 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
176 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
53 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
115 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
39 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
39 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
183 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
59 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
155 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
22 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
171 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
89 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
141 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
117 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
262 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
32 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
69 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 ...
0
votes
0answers
15 views

Want to construct a skew starter for the skew room square of order 667.

If I can obtain a skew starter for the skew room square of order 667 then I can construct the symmetric block design (667,333,166). Then once I have the incidence matrix M for this design, I can then ...
2
votes
0answers
29 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
763 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
134 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$ ...
1
vote
0answers
42 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
0
votes
2answers
81 views

Proved : $3(a+b+c)\geq \sqrt{8a^{2}+1}+\sqrt{8b^2+1}+\sqrt{8c^{2}+1}$

$1$. $x;y;z\in \mathbb{R}$ such that $xyz=1$. Find the minimum or maximum value of : $\sum \dfrac{1}{x+1}$ $2$. $x;y;z\in \mathbb{R}^+$ such that $a+b+c=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}$. Proved ...
2
votes
1answer
37 views

What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
0
votes
1answer
47 views

If $|V(G)|=n$ and $e(G)>\frac{n}{4}\{1+\sqrt{4n-3}\}$ then $G$ contains 4-cycle

This question is linked to my former question Special properties of subgraphs I want to practice this technique a little bit more and want to show that if $|V(G)|=n$ and ...
2
votes
1answer
187 views

Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...