Roudneff‘s Conjecture in Dimension 4

EUROCOMB’23

Rangel Hernández-Ortiz Kolja Knauer Luis Pedro Montejano Manfred Scheucher

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-078

PDF
Abstract
J.-P. Roudneff conjectured in 1991 that every arrangement of $n \ge 2d+1\ge 5$ pseudohyperplanes in the real projective space $\mathbb{P}^d$ has at most $\sum_{i=0}^{d-2} \binom{n-1}{i}$ complete cells (i.e., cells bounded by each hyperplane). The conjecture is true for $d=2,3$ and for arrangements arising from Lawrence oriented matroids. The main result of this manuscript is to show the validity of Roudneff‘s conjecture for $d=4$. Moreover, based on computational data we conjecture that the maximum number of complete cells is only obtained by cyclic arrangements.

Pages:
561–567
References

Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented Matroids, 2nd edition, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1999.
https://doi.org/10.1017/CBO9780511586507

C. Carathéodory. Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. Mathematische Annalen, 64:95-115, 1907.
https://doi.org/10.1007/BF01449883

L. Finschi. Webpage: Homepage of oriented matroids. https://finschi.com/math/om/?p=catom&filter=nondeg.

L. Finschi. A graph theoretical approach for reconstruction and generation of oriented matroids. PhD thesis, ETH Zürich, Switzerland, 2001.

L. Finschi and K. Fukuda. Generation of oriented matroids-a graph theoretical approach. Discrete & Computational Geometry, 27(1):117-136, 2002.
https://doi.org/10.1007/s00454-001-0056-5

J. Folkman and J. Lawrence. Oriented matroids. Journal of Combinatorial Theory, Series B, 25(2):199-236, 1978.
https://doi.org/10.1016/0095-8956(78)90039-4

D. Forge and J. L. Ramírez Alfonsín. On counting the k-face cells of cyclic arrangements. European Journal of Combinatorics, 22(3):307-312, 2001.
https://doi.org/10.1006/eujc.2000.0462

J. Lawrence. Oriented matroids and multiply ordered sets. Linear Algebra and its Applications, 48:1-12, 1982.
https://doi.org/10.1016/0024-3795(82)90094-5

P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17(2):179-184, 1970.
https://doi.org/10.1112/S0025579300002850

L. P. Montejano and J. L. Ramírez Alfonsín. Roudneff's Conjecture for Lawrence Oriented Matroids. Electronic Journal of Combinatorics, 22(2):Paper #P2.3, 4 pages, 2015.
https://doi.org/10.37236/4811

J. L. Ramírez Alfonsín. Cyclic arrangements and Roudneff's conjecture in the space. Information Processing Letters, 71(5):179-182, 1999.
https://doi.org/10.1016/S0020-0190(99)00115-5

J.-P. Roudneff. Cells with many facets in arrangements of hyperplanes. Discrete Mathematics, 98(3):185-191, 1991.
https://doi.org/10.1016/0012-365X(91)90375-C

R. W. Shannon. Simplicial cells in arrangements of hyperplanes. Geometriae Dedicata, 8(2):179-187, 1980.
https://doi.org/10.1007/BF00181486

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Rangel Hernández-Ortiz, Kolja Knauer, Luis Pedro Montejano, Manfred Scheucher

PDF