Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. An extremal problem on crossing vectors
 
research article

An extremal problem on crossing vectors

Lason, Michal  
•
Micek, Piotr
•
Streib, Noah
Show more
2014
Journal Of Combinatorial Theory Series A

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Z(w)? We state a conjecture that the answer is k(w-1). We prove the conjecture for w <= 3 and provide weaker upper bounds for w >= 4. Also, for all k and so, we construct several quite different examples of families of desired size k(w-1). This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set. (C) 2019 Elsevier Inc. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.jcta.2014.07.009
Web of Science ID

WOS:000343529100002

Author(s)
Lason, Michal  
•
Micek, Piotr
•
Streib, Noah
•
Trotter, William T.
•
Walczak, Bartosz  
Date Issued

2014

Publisher

Academic Press Inc Elsevier Science

Published in
Journal Of Combinatorial Theory Series A
Volume

128

Start page

41

End page

55

Subjects

Crossing vectors

•

Maximum antichains

•

Extremal problems

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
December 30, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/109767
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés