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.

Filter by
Sorted by
Tagged with
1
vote
0answers
17 views

Bounds on the number of maximal intersecting families

I am looking for both upper bounds and lower bounds on the number of maximal intersecting families (intersecting families of size $2^{n-1}$) A trivial lower bound is $n+1$ (by considering $\mathcal{A}...
0
votes
1answer
38 views

Formula for How many combinations we can have from two sets with restrictions

Find the formula: Let $A=\{1,2,...,27\}$ and $B=\{28,29, ...,50\}$. How many combinations we can have from two sets: A and B; such that to obtain subsets of 7 elements, where 5 elements belongs to ...
1
vote
0answers
15 views

What is the minimal possible length of an $n$-universal word? [duplicate]

Suppose $A$ is a finite alphabet. Let's call a word $w \in A^*$ $n$ -universal iff it contains every word from $A^n$ as a subword. What is the minimal possible length of an $n$-universal word over $A$?...
0
votes
1answer
100 views

Maximal intersecting family of $X = \{1, \ldots, 7\}$

$X = \{1, \ldots, 7\}$. Give an example of an intersecting family $F$ of maximal size
0
votes
1answer
41 views

In how many different ways can we place $k$ elements in $n$ boxes in which each box has a fixed maximum capacity?

I've been reading and studying about Permutations, Dispositions and Combinations recently. The problem I've facing since yesterday (and I've not been able to find a solution either in my own or on the ...
1
vote
1answer
23 views

In a random graph $G(n,p)$ with $\delta(G) \geq \delta$, how is the event $\{S \subset V \text{ is not a dominating set} \}$ characterized?

This is a problem from my class, with the first part of the solution. I'd like to ask something about the set $S \subset V$ as defined below. Problem: Given $G$ on $n$ vertices with $\delta(G) \geq ...
1
vote
1answer
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 ...
-1
votes
1answer
23 views

Confusion on applying Szemeredi's lemma to graph building etc

I am struggling to understand how we apply Szemeredi's regularity lemma (SRL) for other results like the graph building (counting) lemma and removal lemmas. The statement of SRL is: Let $\epsilon&...
0
votes
1answer
12 views

Assignment problem cost matrix reconstruction justification

I have asked questions numerically on this topic, but here is a theoretical question that i want to ask, if the answer is affirmative, then only can i proceed with my problem. I have an assignment ...
6
votes
1answer
207 views

Let $G$ be an $n$-vertex graph with at most $100n$ triangles. Prove that $G$ has a triangle-free…

Let $G$ be an $n$-vertex graph with at most $100n$ triangles. Prove that $G$ has a triangle-free induced subgraph with at least $\frac{n}{15 \sqrt{3}}$ vertices. My solution: We pick each vertex ...
2
votes
2answers
88 views

How can I find the number of different triangles in $n$-vertex graph?

First of all, I reveal this problem stems from below statement. a graph $G = (V, E)$ with $n$ vertices is extremal for $K_3$ if it contains "no triangles" and has $\left\lfloor\frac{n^2}{4}\right\...
0
votes
0answers
16 views

Calculus of Variation: how to find extremas for the Functional?

I have the functional $I(t)=\int dt\ y^2(1-y')^2$ with the constraints $y(2)=1$ and $y(3) = \sqrt{3}$. I need to find the unique smooth extremal. I used the Euler-Lagrange equation $$\frac{dL}{dy}-\...
3
votes
1answer
152 views

New Character in Chess game

I having problem to solve the below question: Given $2020\times 2020$ chessboard, what is the maximum number of warriors you can put on its cells such that no two warriors attack each other. ...
0
votes
0answers
29 views

Split n numbers into k lists with equal size, which any different combination of m lists contains all the n numbers

I'm triyng to find an answer for this qustion... Lets say I have a range of {0, 1, ... , r} numbers, where I need to choose sub range of n size, which I want to divide into k equal size lists. I can ...
0
votes
1answer
55 views

Permutation: solutions to linear equation: Compute the number of all solutions $(x_1, x_2,\dots, x_n)$ of the equation $x_1+x_2+\dots+x_n=k$

Compute the number of all solutions $(x_1,x_2,\dots,x_n)$ of the equation $x_1+x_2+\dots+x_n=k$ in the case where $x_i\in\{m,m+1\}$, $i= 1,2,\dots,n$, for some natural number $m$. I believe this is ...
0
votes
1answer
30 views

Finding large solution-free sets

(posted on Stack Overflow, but was suggested to post here instead) Is there any nice way to check if a given set has any (nontrivial) solutions to a fixed linear equation? My goal is to find the ...
0
votes
0answers
53 views

3 connected graphs

I am trying to understand the following Lemma: Let G be a 3 connected graph of order at lest five and x in V(G). Suppose degree of x in G is 3 and the set of vertices adjacent to x in G is {a,b,c}. If ...
1
vote
0answers
44 views

Size of a family of subsets of $[n]$, where any two subsets are non-disjointed, none contains the other, and the union of them is not $[n]$.

Let $\mathcal{F} = \{F_1,...,F_m \}$ be a family of subsets of $[n]$, such that for every $i \neq j, F_i \subsetneq F_j, F_i \cap F_j \neq \emptyset, \text{ and } F_i \cup F_j \neq [n]$. Prove that $m ...
1
vote
0answers
31 views

Construct a coloring of the positive integers with finitely many colors such that there is no monochromatic solution to the equation $x + y = 3z$.

I followed a hint but only got a partial solution: we use $4$ colors $a,b,c,d$, and for a number $k$ that is not a multiple of $5$, the coloring function $c(k)$ is determined by $k \text{ mod } 5$: (...
1
vote
1answer
63 views

Edges on $K_{2,m}$ free graph

Q: Let $G=(V,E)$, such that $|V|=n$. G does not contain as a sub-graph a $K_{2,m}$ - complete bipartite graph which one side contains 2 vertices, and the second $m$ vertices. Prove that that the ...
1
vote
1answer
150 views

A problem on the $n\times n$ square [closed]

This problem is stated directly as following Problem A $n\times n$ square that satisfies the following conditions: $n\geq 4$ In each unit square we write a number $x$, with $0\le x \le 1 $. No ...
2
votes
1answer
61 views

If each edge of a graph $G=(V,E)$ belongs to exactly one triangle then $|E|=\omicron(n^{2})$.

Given $\epsilon > 0$, prove the existence of a $n_\epsilon \in \mathbb{N}$ such that, if $G=(V,E)$ is a graph on $n > n_\epsilon$ vertices, and each edge of $G$ belongs to exactly one triangle, ...
1
vote
1answer
34 views

Simplification of the $\epsilon$-regularity condition in graphs.

Let $G = (V,E)$ be a graph, and let $A,B \subset V$ be two disjoint non-empty sets of vertices, of sizes $a$ and $b$ respectively. Show that in order to check whether or not the pair $(A,B)$ is $\...
11
votes
0answers
232 views

Maximizing $\sum_{i,j=1}^{n}|\operatorname{deg}\ x_{i}-\operatorname{deg}\ x_{j}|^{3}$ over all simple graphs with $n$ vertices

For a simple graph $G$ on $n$ vertices, let us define $$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\operatorname{deg}\ x_{i}-\operatorname{deg}\ x_{j}|^{3}$$ I am highly interested in finding $\sup \...
2
votes
0answers
43 views

Show that, if girth$(G) \geq g, \text{and } \delta(G) \geq d$, then $|V(G)|= n = \Omega(d^k), \text{where } k = \lfloor \frac{g-1}{2} \rfloor$.

I only have a rough idea, which I would like to have some comments on. Assume $d \geq 3$. Let $v$ be a vertex of $G$. We observe that any path starting from $v$ must have its ending vertex being ...
3
votes
1answer
103 views

Say a finite set $M$ has two partition $A_1,A_2,…A_p$ and $B_1,B_2,…B_p$ such that …

Say a finite set $M$ has two partitions $A_1,A_2,...A_p$ and $B_1,B_2,...B_p$ such that $$A_i\cap B_j = \emptyset \implies |A_i|+|B_j|\geq p.$$ Prove: $$|M|\geq {1\over 2}(p^2+1).$$ As far as I can ...
0
votes
0answers
24 views

A step in the proof of the degree lemma.

I'm reading this proof of the so-called degree lemma, in connection to Szemerédi's Regularity Lemma. In the last part, in the assumption for a contradiction that $|X| \geq \epsilon |C|$, we have $d(X,...
0
votes
0answers
28 views

Let $G$ be the graph on vertex set $[4]$ with edges $12, 13, 14, 23$ (triangle with a tail). Determine the Turán number $ex(n,G)$ for every $n$.

Please give your comment on the solution below. Let $H$ be a graph on $n$ vertices. My observation is that, if $H$ is triangle-free, then $H$ is also $G$-free. The triangle-free graph with the ...
2
votes
2answers
155 views

Large subgroups of Symmetric Group

Let $n \geq 5$. It is easy to prove that if $H \leqslant S_n$ has index $\leq n$, then $H$ is $A_n$ or $S_{n-1}$. So my question: can this be improved to $n^2$? I mean, if $[S_n:H] \leq n^2$, is it ...
0
votes
1answer
29 views

$S = \{1,2,…,2005\}$, $A = \{a_{1}, …, a_{k}\} \subset S$ with $a_{i}+a_{j}$ not multiple of 125. What is $\max(k)$?

$S = \{1,2,...,2005\}$, $A = \{a_{1}, ..., a_{k}\} \subset S$ with $a_{i}+a_{j}$ not multiple of 125 whenever $a_{i} \ne a_{j}$. What is $max(k)$? Attempt: After exploring, I found that We can put ...
1
vote
1answer
39 views

Parameter $d$ that makes the probability of the graph $G(n,\frac{d}{n})$ being $k$-colorable tends to $0$, as $n \to \infty$ , for $k \leq 2$.

This is an exercise that I'm doing. Let $\epsilon > 0$ and $d > 0$ be fixed. Prove that for $k \geq 2$, if $d \geq (1 + \epsilon)2k(\text{log} k + 1)$, then, $\lim\limits_{n \to \infty} \...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
42 views

Relatively maximal sum-free subsets in finite groups

Suppose $G$ is a group, $S \subset G$. Let’s call $S$ sum-free iff $\forall a, b \in S$ we have $ab \notin S$. What is the value of $c := \sup\{\frac{|A|}{|G|}| $G$ \text{ is a finite group, } A \...
1
vote
0answers
65 views

Maximal subset with given Hamming distances

Suppose $A$ is a finite alphabet, $|A| = n$. Suppose $m \in \mathbb{N}$. Let’s define the Hamming metric on $A^m$ as $d_m(a_1…a_m, b_1…b_m) = |\{i \leq m|a_i \neq b_i\}|$. Now, let’s define $s(n, m, ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
4
votes
1answer
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 ...
0
votes
0answers
25 views

Erdos-Ko-Rado for 3

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$,...
2
votes
2answers
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....
3
votes
2answers
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$.
15
votes
1answer
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$ ...
5
votes
4answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
28 views

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 ...
0
votes
0answers
41 views

Deduce the finite Ramsey theorem from the infinite case.

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, ...

1
2 3 4 5
10