Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGreedy balanced pairs in $N$-free ordered sets
90
0
0.0
(
0
)
Authors
Imed Zaguia
Ask ChatGPT about the research
No Arabic abstract
An $alpha$-greedy balanced pair in an ordered set $P=(V,leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of greedy linear extensions of $P$ that put $x$ before $y$ among all greedy linear extensions is in the real interval $[alpha, 1-alpha]$. We prove that every $N$-free ordered set which is not totally ordered has a $frac{1}{2}$-greedy balanced pair.
rate research
Read More
For a (finite) partially ordered set (poset) $P$, we call a dominating set $D$ in the comparability graph of $P$, an order-sensitive dominating set in $P$ if either $xin D$ or else $a<x<b$ in $P$ for some $a,bin D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $gamma_{os}(P)$, the least size of an order-sensitive dominating set of $P$. For every graph $G$ and integer $kgeq 2$, we associate a graded poset $mathscr{P}_k(G)$ of height $k$, and prove that $gamma_{os}(mathscr{P}_3(G))=gamma_{text{R}}(G)$ and $gamma_{os}(mathscr{P}_4(G))=2gamma(G)$ hold, where $gamma(G)$ and $gamma_{text{R}}(G)$ are the domination and Roman domination number of $G$, respectively. Apart from these, we introduce the notion of a Helly poset, and prove that when $P$ is a Helly poset, the computation of order-sensitive domination number of $P$ can be interpreted as a weighted clique partition number of a graph, the middle graph of $P$. Moreover, we show that the order-sensitive domination number of a poset $P$ exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of $P$. Finally, we prove that the decision problem of order-sensitive domination on posets of arbitrary height is NP-complete, which is obtained by using a reduction from EQUAL-$3$-SAT problem.
A subset of the integer planar grid $[N] times [N]$ is called corner-free if it contains no triple of the form $(x,y), (x+delta,y), (x,y+delta)$. It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrends large subset of $[N]$ with no $3$-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity. In the $3$-players exactly-$N$ problem the players need to decide whether $x+y+z=N$ for inputs $x,y,z$ and fixed $N$. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-$N$ problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.
In this paper, we study product-free subsets of the free semigroup over a finite alphabet $A$. We prove that the maximum density of a product-free subset of the free semigroup over $A$, with respect to the natural measure that assigns a weight of $|A|^{-n}$ to each word of length $n$, is precisely $1/2$.
The closed cone of flag vectors of Eulerian partially ordered sets is studied. It is completely determined up through rank seven. Half-Eulerian posets are defined. Certain limit posets of Billera and Hetyei are half-Eulerian; they give rise to extreme rays of the cone for Eulerian posets. A new family of linear inequalities valid for flag vectors of Eulerian posets is given.
We investigate the relationship between two constructions of maximal comma-free codes described respectively by Eastman and by Scholtz and the notions of Hall sets and Lazard sets introduced in connection with factorizations of free monoids and bases of free Lie algebras.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
