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

4
votes
0answers
19 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
82 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
53 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
24 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
197 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
36 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
35 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
42 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
177 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
170 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
52 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
101 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
32 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
38 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
166 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
49 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
148 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
167 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
85 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
128 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
104 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
208 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
41 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
59 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
14 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
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 ...
5
votes
3answers
461 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
121 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
80 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
178 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, ...
0
votes
1answer
64 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 ...
3
votes
1answer
59 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 ...
2
votes
1answer
144 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. ...
1
vote
2answers
85 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 ...
0
votes
1answer
52 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
61 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
40 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 ...
6
votes
1answer
316 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 ...
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$ ...
5
votes
1answer
135 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
9
votes
3answers
604 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 ...
3
votes
1answer
134 views

Suppose there are k points, no 3 of which are collinear. What is the upper bound on the number of quadrilaterals we can form?

We understand that the number of triangles possible is given by kC3, since any selection of 3 points uniquely determine a triangle. This is not true for quadrilaterals though, since for selections ...
1
vote
1answer
58 views

Has this variation of blocking set been studied before?

Given a collection of sets $F$, a set which intersects all sets in the $F$ in at least one element is called a blocking set (or hitting set). The blocking number $τ(F)$ of a family $F$ is the minimum ...
0
votes
0answers
48 views

An extremal combinatorial problem over Finite rings

Let $q$ be an odd number and $g_i = (g_{i1} g_{i2} \dots g_{ir}) \in \Bbb Z_q^r$ a list of vectors with $i\in\{1,\ldots,L\}$. Let each $g_i$ have $0 < k < r$ zero entries. What is the maximum ...
5
votes
1answer
139 views

Show there’s at most $n\choose \left \lfloor\frac{n}{2} \right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that ...