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

134 views

### Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
8 views

### Turan number for disjoint union of complete graphs

I have been trying to locate literature relating to the Turan number for disjoint union of complete graphs, i.e. $ex(n, tK_r)$, where $K_r$ is the complete graph. My search has so far been ...
32 views

### how to find closely related values from a set?

I have a set of values, for eg. {20, 1, 1, 21, 8, 22, 11, 40, 5, 21} and will need to find n closely related values. If n is 4 in the given example, the result should be {20, 21, 21, 22} because these ...
21 views

I'm trying to solve the following problem: Find the maximum possible size of a set $S \subset \mathbb{F}_q^n$ of codewords satisfying the following three conditions: For every $\mathbf{x}, \mathbf{... 1answer 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 ... 1answer 399 views ### Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ... 3answers 2k views ### Minimum number of integer-sided squares needed to tile an$m$by$n$rectangle. Let$T(m,n)$for integers$m,n$be the least number of integer-sided squares needed to tile an$m\times n$rectangle. Clearly$T(kx,ky)\leq T(x,y)$. Are there integers$x,y,k\gt 1$, such that$T(kx,ky)...
260 views

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)}$, ...
532 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 ...
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)}$ ...
39 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

46 views

33 views

### Toroidal Split Complete Graphs

The paper On the Planar Split Thickness of Graphs shows how non-planar graphs can be split to make planar graphs. For example, they offer a split $K_{6,10}$. I would instead like to make split ...
31 views

### Families of 3-element subsets such that no two intersect more than once

Another user asked the following question: "How can I determine the size of the largest collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements ...
31 views

### Inductive proof of Turan's theorem

I am trying to use induction to show that the maximum number of edges in a graph with $n$ vertices and no $k+1$ clique is \begin{align} (1- \frac{1}{k})\frac{n^2}{2} \end{align} and the unique graph ...
36 views

### Dilworth's theorem application

I need to prove the following: Let $a_1,a_2,...,a_{n^2+1}$ be a permutation of the integers $1,2,...,n^2+1$. Show using Dilworth's theorem or mirsky's theorem that the sequence has a subsequence of ...
27 views

### Lower bound for monochromatic triangles on 2 coloring of $K_n$

I am trying to show that there is at least $\frac{n(n-1)(n-5)}{24}$ monochromatic triangles in any 2 coloring of the edges of $K_n$. I am trying to show this using Mantel's theorem but I can't seem ...
32 views

### Extremal set theory problem concerning translations of a set of integers

Let $A$ be a subset of $B = \{1, 2,\ldots,n\}$. Suppose that $F$ is a family of subsets of $B$, each of which is a translation of $A$ and no two of which intersect more than once. What is the maximum ...
23 views

### Local maximum of $(2^{xy}{z \choose y})^{z+1}$

I have an optimization problem where I need to calculate the maximum of the following function $$f(x,y,z) = (2^{xy}{z \choose y})^{z+1}$$ where $$(z+1)(a+y(\lceil{\log_2{(z+1)}}\rceil+x))\leq C$$ ...
17 views

### Upper bound on the product of independence number and transversal for graph

I am trying to prove if $G$ is an $n$ vertex graph such that $|E(G)| \leq \alpha(G)\tau(G)$, then $|E(G)| \leq \frac{n^2}{4}$ where $\tau(G)$ is the smallest transversal in $G$. A transversal is a ...
26 views

### Allocate Chamber Musicians to Fewest Possible Concerts

First of all, I am not a mathematician. I'm mainly asking the question to see if what I want to do is even possible via math -- and whether I then could computerize this math. So you may throw this ...
60 views

### Size of coefficients of polynomials that satisfy a Chebyshev-like extremal property

The famous Chebyshev polynomials satisfy many extremal properties. One of these is that they attain the largest possible derivative over the interval [-1,1] among polynomials whose absolute value over ...
66 views

### How to convert this proof in probabilistic method setting? [closed]

Suppose we pick $s$ objects independently and at each step probability that object is defective is $1/h$ then probability that each object is not defective $s$ steps is $$(1-1/h)^s$$ which as $h$ ...