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

3
votes
0answers
23 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
13 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
24 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 ...
-3
votes
0answers
33 views

Find the different Binary String [duplicate]

I want to generate a binary String, such that number of occurrence of 01,10,00 and 11 are to be fixed. For Ex: Number of occurrence of 01,10,11 and 10 are 1 1 2 and 1 respectively. ...
1
vote
0answers
31 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
264 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
61 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
49 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
50 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
49 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
18 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
30 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
64 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
38 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
36 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
57 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
23 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
47 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
80 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
48 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
475 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
31 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
279 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
41 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
43 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
37 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
31 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 ...
4
votes
1answer
67 views

Maximum number of size $k$ subsets where no two overlap on more than $e$ elements.

As the title suggests: What is the maximum number of size $k$ subsets of $[1, \dots, n]$ such that no subsets overlap on more than $e$ elements? I only really care about the asymptotics, so an ...
3
votes
1answer
114 views

Lower bound for the chromatic number of $\mathbb{R}^n$

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$: $$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$ At some point in the proof we get that ...
2
votes
1answer
50 views

Combinations with maximum allowed Repetition

There are how many ways to select $r$ things from $n$ categories with maximum $k$ repetitions are allowed from each category? I think its only solvable if and only if $nk\ge r$ and I also believe ...
0
votes
0answers
22 views

To write product of 2 combinations as one combination term

Is it possible to write this product of combinarions as one comination term $\binom{N-x-1}{r} * \binom{x-1}{r} $
1
vote
2answers
49 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
106 views

Inclusion-Exclusion question

A careless payroll clerk is placing employees’ paychecks into pre-labeled envelopes. The envelopes are sealed before the clerk realizes he didn’t match the names on the paychecks with the names on the ...
0
votes
0answers
31 views

How to find the width knowing clique number

For an interval order, clique number=chromatic number (which is the minimum number of colors you can use for each edge to be incident to vertices that are of different colors). I also read that clique ...
0
votes
0answers
9 views

Family of graphs with structural intersection (namely, no isolated vertices)

In the book Extremal Combinatorics: With Applications in Computer Science I found the following theorem: Theorem. Suppose that $\mathcal{F}$ is a family of (labeled) subgraphs of $K_n$ such that for ...
1
vote
3answers
72 views

$K_{3,3}$ an exception to Planar Graph formula

So I have learned that for a graph to be considered Planar, if it has at least 3 vertices, you can apply the following formula to test for planarity: number of edges ≤ 3(number of vertices) - 6 also ...
0
votes
1answer
55 views

Element in chain and antichain

When analyzing one poset graph, can an element be both in the longest chain and the longest antichain? (or do chains and antichains have to be mutually exclusive?)
0
votes
1answer
81 views

Anna and Carlos are discussing a graph with 17 vertices and 129 edges

Anna and Carlos are talking about a graph with 17 vertices and 129 edges. One of them says that it must be a Hamiltonian graph, while the other say's it's not. With no other information about the ...
0
votes
1answer
104 views

Chromatic Number of Trees

All trees with more than one vertex have the same chromatic number. What is it & Why? (Is this chromatic number by any chance 2, by definition of what a tree is? Since a tree is acyclic and ...
0
votes
2answers
189 views

Pigeonhole Principle : $mn+1$ pigeons into $n$ holes.

If you have to put $n+1$ pigeons into $n$ holes, according to Pigeonhole principle, you will have to put two pigeons into the same hole. But what if you have to put $mn+1$ pigeons into $n$ holes? ...
3
votes
0answers
18 views

How should $k$ items be selected in $m$ trials so that the average size of the intersection of selected items is as small as possible?

Let $n$ be size of set of items and in $m$ trials $k$ items are selected from the set without replacement. In two different trials the same items can be selected. How should items be selected so that ...
3
votes
1answer
42 views

Cross intersecting families bound

I have been looking at the following problem Suppose $k,l \geq 1$, $k+l \leq n$ and consider $$\mathcal{A} \subseteq \binom {[n]} l, \mathcal{B} \subseteq \binom {[n]} k$$ Which are cross ...
0
votes
1answer
47 views

Rank notion of a matrix

$\newcommand{\rank}{\operatorname{rank}}$Divide $p-1$ ($p=q^k>2$ with $k>1$, $q$ prime) elements in $\Bbb F_p^\times$ into equal disjoint subsets $S_+,S_-$. Given square $0-1$ matrix $A$, ...
4
votes
4answers
62 views

Integer solutions to this problem

So I have this question, and I know that I need to start off with downgrading $782$ to $762$ (to account for $x_4$ and $x_5$ being equal to $10$). $x_1 +x_2+x_3+x_4+x_5 ≤ 782$ where $x_1,x_2 > ...
2
votes
3answers
60 views

Integer solutions of the following question:

How many integer solutions are there in this equation: $$x_1 + x_2 + x_3 + x_4 + x_5 = 63, \quad x_i \ge 0, \quad x_2 ≥10$$ I got $C(56,3)$. Is that correct?