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

0
votes
0answers
4 views

Family hitting r-sets

I'll start with a definition. We say a family $\mathcal{F}\subseteq [n]^{(k)}$ hits every $r$-set for some $r\geq k$ if for each $R\in[n]^{(r)}$, there exists $F\in \mathcal{F}$ such that $F\subseteq ...
0
votes
1answer
20 views

Does a sum of squares become smaller as the number of terms increases?

I am interested in the following question: Let $,kn$ be a positive integeres. Assume $\sum_{i=1}^{k} L_i=\sum_{i=1}^{k+1} \tilde L_i=n$, where $L_i,\tilde L_i$ are positive integers. Is it true ...
9
votes
2answers
132 views

What's the minimal $k$ satisfying these conditions? Graph theory problem.

I'm thinking following problem. There are five pairs of couples (So, ten people total) and $k$ clubs satisfying following three conditions. Let $A,B$ are arbitrary people among those 10, ...
2
votes
2answers
109 views

Game: Group and Multi-Dimensional Chessboard

Let $G$ be a group and $S\subseteq G$. Consider a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, where $n_1,n_2,\ldots,n_d\in\mathbb{N}$. Each unit hypercube of the ...
2
votes
0answers
48 views

The Crossing Number of a family of graphs which contain the complete bipartite graphs.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
5
votes
2answers
177 views

$n\times n$ chessboard game with coins

The rows and the columns of an $n\times n$ chessboard are numbered $1$ to $n$, and a coin is placed on each field. The following game is played: A coin showing tails is selected. If it is in row ...
0
votes
1answer
384 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 ...
5
votes
1answer
40 views

Maximum number of right-angled triangles

Let $S$ be a set of $n$ points in the plane, no $3$ collinear. Determine the maximum number of right-angled triangles with all three vertices as points in $S$. This is a slightly more difficult ...
1
vote
0answers
21 views

Definition of Quasi-Concave Set Function for an Accessible Set System

Is $F(C(X\cup Y))\ge \min(F(X),F(Y))\ \forall X,Y$ where $(E,\mathbb{F})$ is a set system with $X,Y\in E$ the definition of a quasi-concave set function? $E$ is a set of all possible subsets of ...
2
votes
1answer
42 views

Intersection of k Hamming balls non-empty

Given a natural number $k\geq 1$. Is there always a odd natural number $n>k$ , so that for any k pairwise different boolean vectors $v_1 , v_2 ,\ldots, v_k\in \mathbb{Z}_2^n$ with Hamming distance ...
3
votes
1answer
39 views

Maximize the number of edges in a bipartite graph with no 4-cycles

Consider an undirected bipartite graph which has $n$ nodes in each component such that there are no cycles of length equal to $4$, and such that each pair of nodes has at most $1$ edge between ...
0
votes
1answer
21 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 ...
4
votes
2answers
111 views

Maximum distance between points in a triangle

An equilateral triangle has sides of unit length. a)Show that if five points lie in/on the triangle, then at least two of the points lie no farther than 0.5 units apart. b)Show that 0.5 cannot be ...
0
votes
0answers
12 views

An extremal combinatorics problem

Given $n\in\Bbb N$, $\alpha\geq1$ denote $f(n,\alpha)$ as worst case minimum number of columns among all $n\times n^\alpha$ $0/1$ matrices with every row summing to $>\frac{n^\alpha}2$ that is ...
1
vote
1answer
31 views

Smallest choice cells such that 4 of them are vextex of a parallelogram

Let a chessboard table $2016\times 2016$. We need to find the smallest number $n$ such that for any choice of n cells of the table, we could find four of them such that, centers of such four cells are ...
10
votes
1answer
177 views

Minimum number of circles with 3 neighbors

It is possible to arrange congruent circles on the plane in such a way that no two circles overlap and each circle adjoins exactly three other circles. The picture shows an example with 16 circles. ...
2
votes
0answers
32 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 ...
0
votes
1answer
30 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 ...
0
votes
0answers
25 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 ...
2
votes
1answer
28 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 ...
0
votes
1answer
25 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 ...
3
votes
0answers
30 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 ...
0
votes
0answers
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 $$ ...
0
votes
0answers
15 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 ...
2
votes
0answers
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 ...
1
vote
0answers
54 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 ...
0
votes
1answer
63 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$ ...
11
votes
2answers
301 views

Largest-area shape with diameter 1?

Define the diameter of a shape as the greatest distance between any two of its points. What diameter 1 shape has the greatest area? Is it the circle? I've been looking for the biggest little ...
0
votes
1answer
54 views

Upper bound for a number of subsets of $\{1, \dots, n\}$

Consider $n \leq 2k$ and let $A_1, \dots ,A_m$ be a family of $k$-element subsets of $[n]$ such that $A_i \cup A_j \neq [n] \forall i,j \in [m]$. I want to show that $m$ is bounded above by ...
2
votes
2answers
582 views

Maximum number of pairwise intersections

Let $[n]=\{1,2,\ldots,n\}$ and let $S$ consist of subsets of $[n]$ of cardinality $2$. I would like to find the maximum number of pairwise intersections that $k$ distinct elements from $S$ can have. ...
0
votes
3answers
55 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 ...
1
vote
0answers
52 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 ...
0
votes
0answers
23 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 ...
1
vote
0answers
14 views

Is this a weaker version of Simonyi's Conjecture

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' ...
3
votes
2answers
220 views

Upper bound for the size of a maximal collection of subsets which, pairwise, have at most one common element

Given a finite set $A$ with $n$ elements, what would be a good upper bound for the size of a largest collection $\mathcal{F}$ of subsets of $A$ which satisfy the following condition: Any two elements ...
4
votes
2answers
242 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
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 ...
1
vote
0answers
67 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, ...
1
vote
1answer
78 views

Arranging objects in special way

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 ...
1
vote
0answers
40 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}$$?
0
votes
0answers
37 views

Proofing a multivariate trigonometric inequality

Geometrically, I have strong reasons to believe that the following inequality holds: $\arccos\left(\cos\alpha \cos\beta - \sin\alpha \sin\beta \cos\varphi\right) \leq \sqrt{\alpha^2 + \beta^2 - 2 ...
1
vote
2answers
62 views

No pairs in a list.

This is a difficult problem that I've been thinking for some time with little success and was wondering if anyone will have a look at it for me? First of all I want to clarify something before we ...
0
votes
0answers
24 views

Smallest Sextic Matchstick graph in 3D

In 2D, the Harborth graph is the smallest known quartic matchstick graph. All edges have length 1 and none intersect. In 3D, the octahedron is quartic and the icosahedron is quintic. What is the ...
1
vote
2answers
52 views

Combinatorics problem on the size of A+B

Let $A$, $B$ be finite subsets of $\mathbb{Z}$ with $|A|=n$, $|B|=m$. Denote $A+B=\{a+b:a \in A, b \in B\}$. It's fairly easy to show that $|A+B| \geq n+m-1$. My question is: If $|A+B|=n+m-1$, ...
1
vote
1answer
48 views

A strange scheduling for $K_{24}$.

This question came from a question asked earlier today linked here The question implicitly asked how to make a schedule with his/her class of 24 students such that: 1) Everyday will consist of the ...
1
vote
2answers
84 views

Determine the smallest positive integer $M$

On some planet, there are $2^{N}$ countries $(N \geq 4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1\times 1$ each field being either yellow or ...
12
votes
2answers
509 views

Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be ...
4
votes
0answers
59 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
0
votes
0answers
40 views

Meaningful Extreme value distribution

Extreme value theory (EVT) dictates that the limit distribution of the minimum of the set of i.i.d. Chi-square random varibales $\{C_1,C_2,\cdots,C_n\}$ is Weibull. The Weibull distribution has ...
15
votes
1answer
285 views

Hypercube and Hyperspheres

Let $n,k\in\mathbb{N}$. In this problem, the geometry of $\mathbb{R}^n$ is the usual Euclidean geometry. The lattice hypercube $ Q(n,k)$ is defined to be the set $ \{1,2,...,k\}^n ...