# Questions tagged [extremal-combinatorics]

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.

453 questions
Filter by
Sorted by
Tagged with
17 views

21 views

### Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$

Let $H$ be the graph on $4$ vertices with $5$ edges. Show ex$(n, H)\leq \left\lfloor\frac{n^2+n}{4}\right\rfloor$. You have to use that $\sum_{uv\in E(G)}d(u)+d(v)=\sum_{v\in V(G)}d(v)^2$. I know ...
23 views

16 views

24 views

19 views

### Show that a 3-uniform hypergraph on $n \geq 5$ points, in which each pair of points occurs in the same (positive) number of edges, is not 2-colorable.

Here a graph is called properly colored if all of its edges contain vertices of different colors. I'm not sure that I understand the construction in the question correctly. It seems to me the ...
32 views

### Cups and caps inequality: $f(s,t) \leq {s+t-2 \choose {s-2}}+1$

A sequence of consecutive line segments in $\mathbb{R}^2$ is called a Cap if their slopes are monotonically decreasing, and a Cup if their slopes are monotonically increasing. Let $f(s,t)$ denote the ...
42 views

60 views

### Give a 13x13 square table. Colour S squares in the table such that no four coloured squares are the four vertices of a rectangle. Find maxS.

Give a 13x13 square table (like this) Colour S squares in the table such that no four squares are the vertices of a rectangle. Find the maximum value of S. I have tried Calculate in Two Ways like ...
52 views

### For $t \geq 3$, if $n \geq R^{(3)}(t,t)$, then n points in $\mathbb{R}^2$ always contain either t collinear points, or t points in convex position.

Here $R^{(3)}(t,t)$ is the 3-uniform Ramsey number in the two colors red and blue. I'd like to ask for some hints. I've tried giving the 3-sets of $n$ points a meaningful coloring (e.g. red if the 3 ...
49 views

### Canonical Ramsey theorem in $m$-uniform setting admits $2^m$ canonical colorings.

This is an exercise I'm doing and I'd like some checking or comments. Given a coloring $c: {\mathbb{N} \choose 3} \to C$, a set $S \subset \mathbb{N}$ is said to be (i) rainbow if no two ...
86 views

### Coloring $\mathbb{N}$ with finitely many colors results in monochromatic $x,y,z \in \mathbb{N}$ such that $x+y = z$.

Here are the statements. I have several ideas on how to go about proving them, but I couldn't develop those ideas fully. I'd like to ask for some comments/hints. (i) Show that whenever the natural ...
35 views

### Let $H$ be a $k$-uniform hypergraph, for some $k \geq 2$, such that $|e \cap f| \neq 1$ for any two edges $e,f$. Show that $H$ is two-colourable.

This is an exercise I'm doing. Please have a look at my attempted solution below. In our class we define a proper coloring of a graph $H$ is one where none of the edges is monochromatic. Assume for ...
66 views

### Minimum number of books to fulfill a condition

There is a group of 100 Readers who come together every month to discuss their findings from the books they have read. They discuss in a group of two people. In order to start a discussion between two ...
25 views

Prove for every positive integer r there is some integer N such that for all n > N, if F is a family of subsets of $\{1, 2, \ldots, n\}$ such that $|A| = r$ and $|A\cap B| \geq 3$ for all $A, B \in F$,...
59 views

### Maximum clique in intersection graph of $3$-element subsets of a $9$-element set?

How big is the largest collection of $3$-element subsets of $\{1,\ldots,9\}$ such that every pair of sets intersects nontrivially? I have a hard time visualizing the problem, or getting a grip on it....
134 views

### Maximum number of cycles of length $4$

If a simple graph has $m$ edges, prove that it has at most $\frac{m^2}{2}$ cycles of length $4$.
350 views

### Maximum odd number of subsets, each intersects exactly half of the others

Find the largest positive integer $k$ with the following property $-$ there exist $2k+1$ distinct subsets of $\{1,\ldots,20\}$ such that each such subset intersects precisely $k$ of the other $2k$ ...
294 views

### black and white grid [closed]

Some squares of a $n \times n$ table ($n>2$) are black, the rest are white. In every white square, we write the number of the black squares having at least one vertex with it. Find the max possible ...
15 views

### Proof of canonical Ramsey theorem by colour patterns of $4$-sets.

I'm reading this proof (theorem 1.5) of the canonical Ramsey theorem, which analyses the colour patterns of the subsets of $4$ elements of $\mathbb{N}$. I'd like to ask for some clarification. In ...
60 views

### How can I construct a $(v,\Bbb{N}_{\geq 6},1)$ pairwise balanced design?

I have recently answered this question, in which I described how solving a puzzle in group testing is related to constructing a block design. But I did not succeed in providing a better answer to the ...
### Lower bound of the Ramsey number $R(k,l)$ using probabilistic argument.
I'd like some hints for the following exercise. My guess is that the RHS is the number of vertices of a graph without a red $K_l$ or a blue $K_k$. If we interpret $p$ as the probability that an edge ...
I'd like to ask for some checking of my proof for the statement below. Using the fact that every $\textbf{red/blue}$ colouring of $\mathbb{N} \choose 2$ contains an infinite monochromatic clique, ...