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
13 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
21 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 ...
2
votes
2answers
110 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 ...
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 ...
5
votes
2answers
178 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 ...
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
0answers
49 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$ ...
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 ...
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 ...
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 ...
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 ...
0
votes
0answers
13 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 ...
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 ...
4
votes
2answers
113 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 ...
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 ...
0
votes
0answers
26 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
30 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 ...
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 ...
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
55 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 ...
11
votes
2answers
304 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
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$ ...
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 ...
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' ...
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
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}$$?
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 ...
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
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 ...
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 ...
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 ...
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 ...
3
votes
1answer
44 views

Equality of unions of subsets of finite set

For $n \in \mathbb{N}$, let $\alpha_n$ be the biggest number such that there exist $\alpha_n$ subsets $M_1, \dots, M_{\alpha_n} \subseteq \{1, \dots, n\}$ with the property \begin{equation*} M_{i_1} ...
3
votes
1answer
64 views

Dependency of submatrix used in a combinatorial strategy .

This is a verification post , Please inform if anything is undefined or unclear or miss-tagged. Also if you vote up/down it would be helpfull if you leave a comment. Introduction: Given a matrix A ...
1
vote
1answer
55 views

Numbers written into a square grid

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem: "The integers from 1 to $n^2$ are written into a ...
11
votes
4answers
1k views

N gunmen in a field

Let n be an odd integer. In some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. ...
2
votes
0answers
43 views

Turan's theorem for balanced r-partite graphs

I'm curious about the following restricted version of Turan's theorem: Among all $r$-partite graphs that are balanced (exactly $n/r$ nodes per part), what is the maximum size of a graph with no ...
0
votes
0answers
32 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...