# Tagged Questions

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.

14 views

36 views

### Does the complete graph contain the maximum number of simple cycles?

Let $\mathcal{G}(n,m)$ be the set of connected, simple graphs with $n$ vertices and $m$ edges. For any graph $G$ we denote its number of simple cycles with $\mu(G)$ and and for any finite family of ...
39 views

### Prove : Each distinct $R_{k,e}$ can appear maximum $\sqrt b \leq n^{3}$ times.

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
40 views

### prove that the minimum number of trails in an odd graph is n/2

In my HW assignments I was asked to prove that If a graph G consists of only odd degree vertices, then the minimum number of trails that decompose it (without having any common edge between each two ...
23 views

13 views

24 views

### Upper bound for amount of distinct subsets

I have the following problem. Let the sets $A_i$, $1 \leq i \leq k$ be distinct subest of $\{1,2,...,n\}$. Suppose $A_i \cap A_j \neq \emptyset$ for all $i$ and $j$. Show that $k \leq 2^{n-1}$ and ...
46 views

56 views

### Minimum value of $x^2+y^2$

The problem is as follows: Find the values of $x,y$ for which $x^2+y^2$ takes the minimum value where $(x+5)^2+(y-12)^2=14$. I was trying to solve it using the extremal principle. But, I couldn'...
55 views

### Olympiad problem similar to Sperner's theorem, inspired by OMM 2 ( unproven conjecture of mine)

This problem is inspired by problem 2 here. Consider a set of cubes $F$, such that each corner $(x,y)$ of any given cube of $F$ satisfies $0\leq x,y \leq n$, and each cube has a corner with ...
25 views

### Set of permutations in which every pair of elements is contained in some cycle

Fix $s,k \in \mathbb{N}$ and let $S_n$ denote the symmetric group of permutations. I am considering permutations $\sigma_1, \dots, \sigma_s \in S_n$ having cycles of size at most $k$ in their disjoint ...
So, I'm aware of Simonyi's conjecture which says that if $\mathcal{A}, \mathcal{B} \subset \mathcal{P}(n)$ satisfy the conditions: $$\forall A,A'\in\mathcal{A} \mbox{ and } \forall B, B' \in\mathcal{... 0answers 31 views ### Number of connected sets intersecting a given set in \mathbb{Z}^d Let A \subset \mathbb{Z}^d and let |A| be its cardinality. Let F_n(A) be the number of connected sets of \mathbb{Z}^d having cardinality n and intersecting A in at least one site. Assume ... 0answers 68 views ### Squared distances 1 to 10 Consider these five points in 6-space. {{1,2,3,4,5,6}, {1,2,3,4,6,5}, {1,2,5,3,4,6}, {2,1,3,5,6,4}, {2,1,6,4,5,3}} Half the squared distances between pairs of these points are 1, 2, 3, 4, 5, 6, 7, ... 0answers 41 views ### Erdos-Ko-Rado Theorem for r subsets Let F be a n-element set, where n is finite, and every r subsets intersect. How can I prove that$$|F| \leq {n \choose k} - {n - r + 1 \choose k}?
Imagine there is a cinema hall and there are $n$ seats and we want to arrange $n$ people with some special conditions on our seats. Each people have number from $1$ to $n$ and clearly our seats is ...