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
14 views

Trimming down a relation to a partial order

Is there any general approach for trimming a reflexive relation to a partial order on a finite set? In particular, given a relation R defined on a finite set, which is reflexive xRx, and for all x $\...
0
votes
0answers
9 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 ...
7
votes
3answers
143 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 ...
1
vote
1answer
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 ...
0
votes
0answers
21 views

The maximum number of codewords which have coordinates differing by 1

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{...
3
votes
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 ...
1
vote
1answer
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)}$ ...
0
votes
1answer
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 ...
1
vote
0answers
23 views

An extemal combinatorial design question. “Weak” steiner stystems.

A Steiner system $S(t,k,\nu)$ is a collection $X$ of $\nu$ points and a collection of subsets of $X$ of size $k$ (frequently called blocks) such that each $t$ element subset of $X$ occurs in exactly $...
0
votes
0answers
32 views

On random subset combinatorics.

Suppose we have $2^n$ elements in a set. We have $cn^\beta$ random subsets of cardinality $\frac{2^n}{c}$ elements each where $c,\beta>1$ holds. Fix a random subset of $n^\alpha$ elements $A$ ...
0
votes
0answers
18 views

n-critical graph with order n+2

Problem: Let G be an $n$-critical graph of order $n+2$. Show that $\overline{G}$ consists of $C_5$ and some isolated vertices. What I've managed to do: Not much, since I don't have many tools at my ...
1
vote
1answer
36 views

Is there a graph with $n$ vertices and $n^2/4$ edges that isn't bipartite? [closed]

Is there a graph with $n$ vertices and $\lfloor n^2/4\rfloor$ edges that isn't bipartite and contains no triangles ($K_3$)? Rather, what I am asking is whether Mantel's Theorem implies that every ...
2
votes
0answers
87 views

How to maximize this set function!?

Given a set $F$ and a function $p: 2^F \times 2^F \to [-1,0] $ such that $p (A \cup B, C) \leq p (A,C) $ for any sets $ A, B, C \in 2^F $ : Q1: How can we choose a non-empty set $O \in 2^F $ such ...
0
votes
0answers
39 views

probability of a random vector in row space of a random matrix

Suppose we have a random matrix $A$ of dimension $n\times m$ (let $m<n$) with entries in $F_2$ ( each entry in $A$ is 0/1 with probability 1/2). Suppose I fix a $x\in \{0,1\}^m$ and $k\in \{1,\...
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
22 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
113 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
50 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 and ...
5
votes
2answers
184 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 $x$ ...
9
votes
2answers
134 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
52 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
46 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 them. ...
1
vote
0answers
24 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
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 ...
2
votes
1answer
46 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
14 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
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 ...
5
votes
2answers
159 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
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
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
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 ...
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
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 ...
11
votes
2answers
346 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 ...
7
votes
4answers
176 views

How many acute triangles can be formed by 100 points in a plane?

Given 100 points in the plane, no three of which are on the same line, consider all triangles that have all their vertices chosen from the 100 given points. Prove that at most 70% of those triangles ...
0
votes
1answer
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$ ...
0
votes
1answer
61 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 $(1-\frac{...
0
votes
3answers
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'...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
15 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' \in\mathcal{...
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
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, ...
1
vote
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}$$?
1
vote
1answer
80 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 ...