Extremal combinatorics describes structures of maximal size under some constraints. For example, how many triangles can a graph contain, and how does it look? How big can a family of subsets of a set be if any two of them must intersect?
2
votes
1answer
29 views
minimum lines, maximum points
There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these ...
0
votes
1answer
132 views
total number of different mixes
Patient Age Avg Visits / Year
<1 year 7.5
1-4 years 3.0
5-14 years 1.8
15-24 years 1.7
25-44 years 2.6
45-64 years ...
1
vote
1answer
15 views
Find maximum size of set family, where at least one member has at least one of any three points, but do not contains all those three points
Let $n$ and $s$ be non-negative integers such that $n\geq 3$ and $2s\log2>3\log n$. Prove that there exists sets $A_1,A_2,\ldots,A_s \subseteq [n]$ such that
for every $B\in \binom {[n]} 3$ there ...
4
votes
1answer
129 views
No induced ordered graph yields large clique/stable set in ordered graph
Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
0
votes
1answer
17 views
Maximum size of k-uniform set family that satisfies a condition
Let n $\leq$ 2k and $A_1,A_2,...,A_m \subseteq [n]$ be distinct k-uniform set where $A_i\cup A_j \neq [n] for all 1 \leq i < j \leq m $. Prove that
$m \leq (1-k/n) \binom n k$
and that equality ...
1
vote
1answer
30 views
Multiples of one number in base-$10$ [duplicate]
How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones?
For example, let $n=3$ then, exists al least one number, the ...
3
votes
3answers
274 views
Demonstration using the Pigonhole principle
I was thinking about the following problem:
Let $n\in\mathbb N$ be odd. If I have a symmetric matrix in $M_n(\mathbb{N})$, i.e. a square symmetric matrix of size $n$, for which each column and ...
0
votes
3answers
50 views
About ascending numbers
I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$
How can I find ...
0
votes
1answer
60 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 ...
2
votes
0answers
45 views
Problem involving set systems - combinatorics.
The question is as follows:
$A \subset \mathbb{P}(X)$
is
called
a
cross-cut
if
for
every
$B \subset X$
there
exists $A' \in A$
with
$B \subset A'$ or
$A' \subset B$. Prove
that
every
cross-cut
...
6
votes
1answer
62 views
Two subsets and their union have same color
Color all nonempty subsets of $[n] = \{1,2,\ldots,n\}$ with colors $1,2,\ldots,r$.
Show that, for all large enough $n$, there exist two disjoint nonempty subsets $A,B \subseteq [n]$ such that ...
3
votes
1answer
66 views
Intersecting set systems and Erdos-Ko-Rado Theorem
Suppose you have an $n$-element set, where $n$ is finite, and you want to make an intersecting family of $r$-subsets of this set. Each subset has to intersecting each other subset.
We may assume $r$ ...
8
votes
1answer
180 views
Small cycles in an undirected graph
Let $G=(V,E)$ be an undirected graph. I am using the usual convention that $n=|V|, m=|E|$. For $v \in V$, let $deg(v)$ be the degree of the vertex $v$.
I am trying to show that if we have $m > ...
4
votes
1answer
116 views
optimal sorting
I got a solution to the following question, but am unable to provide a proof.
Given 25 distinct integers, one can sort them 5 at a time. What is the least number of sorting to obtain the smallest 3 ...
0
votes
1answer
78 views
Walks on the Integer Grid
Consider the set of all walks with $2k$-many steps on the integer grid starting from the point $n \in \mathbb{Z}$ and turning back to this specific point. Let each walk is of lenght $\pm 2$ and do not ...
0
votes
0answers
40 views
Computation efficient recursive pairing function
Cantor pairing function is really one of the better ones out there considering its simple, fast and space efficient, but there is something even better published at Wolfram by Matthew Szudzik, here.
...
-2
votes
1answer
90 views
question challenge expert math
I have question. this question is need more explain can anyone do
if we have $$k_n=a_n+a_{n-1}+a_{n-2}+ \dots+a_1+a_0$$
where $a_n=1$ only $n$ is a multiple of $5$, $0$ otherwise. So
$$k_n= ...
0
votes
1answer
37 views
Calculating amount of t/r tickets for crews working in shifts 4 weeks out 2 weeks home
I want to calculate how many flight tickets I would need to buy if I have a total of 6 men working in three (3) teams two (2) at the time at a building site for 4 weeks in a row that is projected to ...
0
votes
1answer
63 views
Question in discrete mathematics *
I have question. Can anyone able to explain to me this problem why if we have 5x the generating function $1+x^5+x^{10}+x^{15} + \ldots$
we have 5 is just constant and multiply with $x$ I know that $x$ ...
1
vote
1answer
65 views
question in discrete mathematics
I have questions. Can anyone help me to get the idea or figure out this problem.
Find a recurrence relation.
If an denote the number of words from the alphabet W={A,B,C} of length n with no two ...
2
votes
0answers
45 views
Ramsey Theory Problem
Let $C(s)$ be the smallest $n$ such that every connected graph on $n$ vertices has, as an induced subgraph either a complete graph $K_{s}$, a star $K(1,s)$ or a path $P_{s}$ of length $s$. Show that ...
1
vote
1answer
249 views
Ramsey-type result for tournaments
I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help.
Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
10
votes
1answer
260 views
Sperner's theorem on antichains - where does it come from?
Sperner proved in 1927 (the paper was published in 1928) his theorem stating that the maximal size of an antichain of subsets of $[n]$ is $\binom{n}{n/2}$. In the introduction to his paper, he ...
4
votes
0answers
54 views
Points at Integer Distances in 3-space
With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1]
For ...
1
vote
0answers
71 views
Does anyone know any specific example of such point set
Does anyone know any specific or explicit example of a set of $256$
points so that no $10$ are the vertices of a convex $10$-gon?
Thanks in advance.
14
votes
2answers
174 views
For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?
$\text{ex} (n;G)$ is the maximal number of edges of a graph of order $n$ can have without containing $G$ as a subgraph.
There are theorems saying what the limit actually is. But my lecture notes ...
2
votes
2answers
77 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 ...
0
votes
2answers
71 views
Bounds for maximal blowup contained in graph
In my homework, I'm asked to prove the following:
By denoting $b_n(r,\epsilon)$ - the largest integer $b$ so that any graph with $(1-\frac{1}{r} +\epsilon)\frac{n^2}{2}$ edges, contains a $b$-blowup ...
4
votes
1answer
58 views
Bound with biclique covering
This concerns a problem from Extremal Combinatorics by Jukna that I cannot solve myself.
First some preliminaries. A biclique covering of a graph is a covering of a graph with complete bipartite ...
12
votes
3answers
947 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 ...
5
votes
1answer
147 views
Almost all labeled graphs implies almost all graphs?
I would be thankful if someone could verify the following reasoning.
Let $I$ be some graph property that is invariant (chromatic number, connectedness,etc.). Let $p(n)$ be the number of (labeled) ...
1
vote
1answer
108 views
Upper bound for the number of open disks containing $k$ points in the plane
I hope that you can help me with this.
Let P be a set of points in the plane, such that $|P|=n$, what is the maximal number of open disks containing at least $k$ points for some $k$, two discs are ...
3
votes
2answers
204 views
Chess Board and Knights
I can't solve this question. anyone knows how I must solve?
You have a 6x3 chess board. How many forms exist to put a Knight in a square and with valid moviments pass in all squares but only one time ...
1
vote
0answers
38 views
Maximum size of a Sperner family containing a set of a given size
Given a set $A$ of $n$ elements and an positive integer $k\le n$, what is the size of the largest Sperner family $\mathcal{F}$ of subsets of $A$ such that $\mathcal{F}$ contains a set $B\subseteq A$ ...
1
vote
0answers
68 views
minimum union of subcubes
Let $B = \{0,1\}^n$ denote the boolean cube containing all $2^n$ binary vectors of size $n$. Let $D_v^s$ be a $d$ dimensional subcube of $B$ where the $d$-coordinates given by $s$ ($s \in [n]^d$) are ...
0
votes
0answers
30 views
edge isoperimetric problem for dual of hypercubes
Are there known results of the form that given a hypercube graph $G= (V,E)$ and a positive integer $m$, list all subsets $A \subset V $ with minimum cardinality such that the edge boundary $\delta(A)$ ...
13
votes
3answers
342 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 ...
0
votes
1answer
236 views
Proof of Turan's theorem
I'm following the proof of Turan's theorem on $\text{ex}(n,K^r)$ in Diestel's Graph Theory book (click to see the page) and something bothers me:
Since $G$ is edge-maximal without a $K^r$ ...
3
votes
0answers
39 views
Internal angle of a vertex of degree $d$ in $\mathbb{E}^2$ and $\mathbb{S}^2$
I am currently working on determining the maximum number of times the minimum spherical distance can occur among $n$ points in $\mathbb{S}^2$, and I have the following question.
In $\mathbb{E}^2$, ...
1
vote
1answer
75 views
How many nodes before k-clique or k-anti-clique?
I am attempting to solve some problems here. For exercise 1, the tightest result I could get is $4^k$. Is that the mininum possible bound?
I am trying to either find a tight example, or find a better ...
2
votes
1answer
118 views
Bounds on the size of these intersecting set families
Are there good lower bounds on the size of a collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common?
1
vote
0answers
120 views
Estimation for ramsey number $R(3,k)$.
Previously I have shown that for any positive integers $k,l$, and any real number $p\in (0,1)$, ramsey number $R(l,k) \geq n- {n\choose k} p^{{k \choose 2}} - {n\choose l} (1-p)^{{l \choose 2}}$.
Now ...
5
votes
1answer
143 views
Graph with 10 nodes and 26 edges must have at least 5 triangles
This is not a homework question, but I would appreciate if people would treat this as if it were homework. I am looking for (nonspoiler) hints.
I would like to prove that given any graph with 10 ...
1
vote
1answer
89 views
What is the maximum point for which number of way to reach is given
Previous question: link
Say there are two points $P_1(a_1,b_1)$ and $P_2(a_2,b_2)$, the number of ways of reaching $P_1$ from the origin is $w_1$ and $P_2$ from $P_1$ is $w_2$. (Here $a_1<a_2$ and ...
2
votes
1answer
187 views
Algorithm to find a permutation that contains the fewest possible monotone subsequences of length $k$
Fix natural numbers $k,n$, with $k<n$. I want to find a permutation in $S_n$ that contains fewest monotone (increasing or decreasing) subsequences of length $k$.
For example the permutation ...
1
vote
1answer
143 views
How do I approach this combinatorics problem about composition?
The question is from Bogart's
A composition of the integer k into n parts is a list of n
positive integers that add to k. How many compositions are there of
an integer k into n parts.
To ...
2
votes
1answer
145 views
Remark on Turán's Theorem
In my notes, Turán's Theorem is stated as follows:
Theorem: Let $G$ be a graph on $n$ vertices. Then $e(G) > e(T_{r-1}(n)) \implies G \supset K_r $.
There are then several remarks on the theorem, ...
3
votes
1answer
160 views
Minimal generation for finite abelian groups
Let $G$ be a finite abelian group. I know of two ways of writing it as a direct sum of cyclic groups:
1) With orders $d_1, d_2, \ldots, d_k$ in such a way that $d_i|d_{i+1}$,
2) With orders that are ...
7
votes
3answers
126 views
Extremum task in combinatorics
Let $\mathbf{M} = \{M_1, M_2, ..., M_s\}$ be a set of (some) 3-element subsets of an $n$-element set.
It is known that $\forall i,j:\quad 1 \leq i \leq j \leq s: \quad |M_i\cap M_j|\neq 1$.
I need ...
7
votes
2answers
633 views
chromatic number of a graph versus its complement
What can be said about the rate of growth of $f(n)$, defined by
$$f(n) = \min_{|V(G)|=n} \left[ \chi(G) + \chi(\bar{G}) \right],$$ where the minimum is taken over all graphs $G$ on $n$ vertices.
Two ...
