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
24 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
30 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
34 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$ ...
0
votes
1answer
382 views

total number of different mixes

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 2.6 45-64 years ...
4
votes
3answers
154 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 ...
14
votes
4answers
440 views

If any triangle has area at most 1 , points can be covered by a rectangle of area 2.

I am working on this problem for some time, and I am not able to finish the argument: There is a finite number of points in the plane, such that every triangle has area at most 1. Prove that the ...
8
votes
2answers
166 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
50 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 ...
8
votes
2answers
155 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
70 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 ...
2
votes
2answers
141 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 ...
0
votes
1answer
29 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
2answers
83 views

Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
2
votes
1answer
115 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
29 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 ...
0
votes
1answer
62 views

Convergence of $\text{ex} (n;P)/ \binom n2$ for Petersen graph

This question is linked to For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge? where an argument was given that this specific ratio converges for ...
6
votes
1answer
274 views

Minimum number of lines covering n points

Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane. My initial approach started like this, 1) for each point I ...
1
vote
1answer
58 views

beads in a string with restrictions

Using the principle of inclusion and exclusion; let $p,q\in \mathbb{N}$, being $p$ odd, there are $pq$ beads of $q$ different colors, with $p$ beads in each color. If the beads of the same colour are ...
1
vote
1answer
42 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 ...
1
vote
0answers
18 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$, ...
2
votes
1answer
78 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 ...
1
vote
1answer
62 views

Maximum size of k-uniform set family that satisfies a condition

Let $n \leq 2k$ and $A_1,A_2,...,A_m \subseteq [n]$ be distinct $k$-uniform set where $A_i\cup A_j \neq [n]$ for all $1 \leq i < j \leq m $. Prove that $$m \leq (1- \frac{k}{n}) \binom n k$$ ...
4
votes
1answer
159 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)}$, ...
9
votes
3answers
525 views

How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
2
votes
1answer
137 views

LYM Inequality question

Suppose that $F ⊂ P(n)$ is a set system containing no chain with $k + 1$ sets. Prove that $\sum\limits_{r=1}^n \frac{|F_{r}|}{n \choose r} ≤ k$, where $F_{i} = F \cap [n]^{(i)}$ for each i. ...
10
votes
1answer
120 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
84 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
161 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
30 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
37 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
54 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
13 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 ...
-3
votes
1answer
48 views

Min $A=14(a^{2}+b^{2}+c^{2})+\frac{ab+bc+ac}{a^{2}b+b^{2}c+c^{2}a}$? [closed]

$a;b;c\in \mathbb{R}^+$ such that $a+b+c=1$. Find the minimum of $A=14(a^{2}+b^{2}+c^{2})+\frac{ab+bc+ac}{a^{2}b+b^{2}c+c^{2}a}$
2
votes
0answers
28 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 ...
2
votes
1answer
257 views

Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$

Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$. For example the permutation ...
5
votes
3answers
409 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 ...
6
votes
2answers
104 views

Two subsets and their union have same color

Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$. Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
1
vote
0answers
39 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
79 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
36 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 ...
2
votes
1answer
166 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, ...
14
votes
3answers
260 views

For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?

$\text{ex} (n;G)$ is the maximal number of edges of a graph of order $n$ can have without containing $G$ as a subgraph. There are theorems saying what the limit actually is. But my lecture notes ...
0
votes
1answer
41 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 ...
3
votes
1answer
54 views

Minimum boolean lattice containing all poset of fixed size

I need help with the following: What is the minimum $n$ such that the boolean lattice $2^{[n]}$ contains all posets of size $m$? I noticed that it should contain a chain of length $m$, and the ...
0
votes
1answer
45 views

Shadow of a set system

I'm currently learning something about Sperner's Lemma and then the LYM Inequality. In trying to prove the LYM Inequality, the proof uses the concept of a shadow but I can't seem to get a proper grip ...
2
votes
1answer
58 views

Maximal rectangle in a permutation

Suppose you have a permutation of n elements, and it is represented by colouring squares in a n by n grid of squares, where only one square is coloured in each row or column. Find the minimum area of ...
1
vote
1answer
38 views

Balanced independent sets & independent domination number

Let $G=(V,E)$ be a bipartite graph, with partition $V=A \cup B$. Recall that an independent set $I$ of $G$ is a set of vertices sharing no edges. The independent domination number $i(G)$ is defined ...
2
votes
1answer
36 views

Error correcting binary partition

Let's say I have a collection of $2^n$ labeled objects, and I want to find one of them. If I can ask yes-no questions about it, binary partition would immediatly lead us to the desired object in $n$ ...
7
votes
1answer
192 views

Minimum cardinality of a difference set in $\mathbb R^n$

Given a finite set $S$ of $m$ points in $\mathbb R^n$ that do not all lie in the same $(n-1)$-dimensional hyperplane, consider the set of difference vectors: $\{x-y \, | \, x,y \in S\}$ What is the ...
0
votes
0answers
67 views

Intersecting Set Systems

This a follow up question to an earlier question: "Intersecting set systems and Erdos-Ko-Rado Theorem " that was answered by Sean Eberhad. It asks, what is the largest intersecting family of r-sets ...