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. A simple proof for a forbidden subposet problem
 
research article

A simple proof for a forbidden subposet problem

Martin, Ryan R.
•
Methuku, Abhishek  
•
Uzzell, Andrew
Show more
January 24, 2020
Electronic Journal Of Combinatorics

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1) <= x(2) <= ... <= x(k) <= y(1), y(2). The poset Y-k,Y-2' is the dual poset of Y-k,Y-2. The sum of the k largest binomial coefficients of order n is denoted by Sigma(n, k). Let La-#(n, {Y-k,Y-2, Y-k,Y-2') be the size of the largest family F subset of 2([n]) that contains neither Y-k(,2) nor Y-k,Y-2' as an induced subposet. Methuku and Tompkins proved that La-#(n,{Y-2(,2), Y-2,Y-2'}) = Sigma(n, 2) for n >= 3 and conjectured the generalization that if k >= 2 is an integer and n >= k +1, then La-#(n, {Y-k,Y-2, Y-k,Y-2'}) = Sigma(n, k)) . On the other hand, it is known that La-#(n, Y-k,Y-2) and La-#(n, Y-k,Y-2') are both strictly greater than Sigma(n, k). In this paper, we introduce a simple approach, motivated by discharging, to prove this conjecture.

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.37236/7680
Web of Science ID

WOS:000513910100015

Author(s)
Martin, Ryan R.
Methuku, Abhishek  
Uzzell, Andrew
Walker, Shanise
Date Issued

2020-01-24

Publisher

ELECTRONIC JOURNAL OF COMBINATORICS

Published in
Electronic Journal Of Combinatorics
Volume

27

Issue

1

Article Number

P1.31

Subjects

Mathematics, Applied

•

Mathematics

•

subset-of-c

•

families

•

bounds

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
March 5, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/166995
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