Search

The interval count problem, a classical question in the study of interval orders, was introduced by Ronald Graham in the 1980s. This problem asks: given an interval order $P$, what is the minimum number of distinct interval lengths required to construct an interval representation of $P$? Interval orders that can be represented with just one interval length are known as semiorders, and their characterizations are well known. However, the characterization of interval orders that require at most $k$ interval lengths -- termed $k$-count interval orders -- remains an open and challenging problem for $k\geq 2$. Our investigation into $2$-count interval orders led us naturally to consider a related problem, interval representations of permutations, which we introduce in this paper. Specifically, we characterize permutations that have a $2$-count interval representation. We prove that a permutation admits a $2$-count interval representation if and only if its longest decreasing subsequences have length at most $2$. For larger values of $k$, however, a similar characterization does not hold. There are permutations that do not permit a $3$-count interval representation despite having decreasing subsequences of length at most $3$. Characterizing $k$-count permutations remains open for $k \geq 3$. The $k$-count permutation representation problem appears to capture essential aspects of the broader problem of characterizing $k$-count interval orders. To support this connection, we apply our findings on interval representations of permutations to demonstrate that a height-$3$ interval order is $2$-count if and only if it has depth at most $2$, where the depth of an interval order refers to the length of the longest nested chain of intervals required in any interval representation of the order.

The length polyhedron $Q_P$ of an interval order $P$ is the convex hull of integral vectors representing the interval lengths in interval representations of $P$. This polyhedron has been studied by various authors, including Fishburn and Isaak. Notably, $Q_P$ forms a pointed affine cone, a property inherited from being a projection of the representation polyhedron, a structure explored also by Doignon and Pauwels. The apex of the length polyhedron corresponds to Greenough's minimal endpoint representation, which is, in fact, the length vector of the canonical interval representation -- an interval representation that minimizes the sum of the interval lengths. Building on a combinatorial perspective of canonical representations, we refine Isaak's graph-theoretical model by introducing a new and simpler directed graph. From directed cycles of this key digraph, we extract a linear system of inequalities that precisely characterizes the length polyhedron $Q_P$. This combinatorial approach also reveals the unique Hilbert basis of the polyhedron. We prove that the intersection graph of the sets corresponding to these binary rays are Berge graphs; therefore they are perfect graphs. As a result, for interval orders with bounded width, the length polyhedron has a polynomial-sized Hilbert basis, which can be computed in polynomial time. We also provide an example of interval orders with a Hilbert basis of exponential size. In a companion paper we determine the Schrijver system for the length polyhedron. We conclude with open problems.

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\'edi and Petruska proved $n\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n \leq {m+2 \choose 2}$. This problem is known to be equivalent to determining the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$ (details may also be found in a companion paper: arXiv:2204.02859). The best known bound, $n\leq \frac{3}{4}m^2+m+1$, was obtained by Tuza using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemer\'edi and Petruska with the skew version of Bollob\'as's theorem on set pair systems. The new approach improves the bound to $n\leq {m+2 \choose 2} + O(m^{{5}/{3}})$, resolving the conjecture asymptotically., Comment: 23 pages, no figures. Completes project begun in "On a conjecture of Szemer\'edi and Petruska", arXiv:1904.04921v2

Recently we asymptotically resolved the long-standing Szemer\'edi and Petruska conjecture. Several decades ago Gy\'arf\'as et al. observed, via a straightforward but unpublished argument, that this conjecture is equivalent to the problem of determining the maximum order of a $3$-uniform $\tau$-critical hypergraph. Consequently, an asymptotically tight upper bound for the maximum order of a $3$-uniform $\tau$-critical hypergraph follows from our recent work, reawakening interest in this equivalence. In this companion paper we supply a simple proof of this equivalence. We also present related background with open problems, and mention combinatorial geometry applications of the Szemer\'edi and Petruska conjecture.

Let H be a 3-uniform hypergraph of order n with clique number k such that the intersection of all maximum cliques of H is empty. For fixed m=n-k, Szemer\'edi and Petruska conjectured the sharp bound $n\leq {m+2\choose 2}$. In this note the conjecture is verified for m=2,3 and 4.

We develop a simple 3-dimensional iterative map model to forecast the global spread of the coronavirus disease. Our model contains at most two fitting parameters, which we determine from the data supplied by the world health organisation for the total number of cases and new cases each day. We find that our model provides a surprisingly good fit to the currently-available data, which exhibits a cross-over from exponential to power-law growth, as lock-down measures begin to take effect. Before these measures, our model predicts exponential growth from day 30 to 69, starting from the date on which the world health organisation provided the first `Situation report' (21 January 2020 $-$ day 1). Based on this initial data the disease may be expected to infect approximately 23% of the global population, i.e. about 1.76 billion people, taking approximately 83 million lives. Under this scenario, the global number of new cases is predicted to peak on day 133 (about the middle of May 2020), with an estimated 60 million new cases per day. If current lock-down measures can be maintained, our model predicts power law growth from day 69 onward. Such growth is comparatively slow and would have to continue for several decades before a sufficient number of people (at least 23% of the global population) have developed immunity to the disease through being infected. Lock-down measures appear to be very effective in postponing the unimaginably large peak in the daily number of new cases that would occur in the absence of any interventions. However, should these measure be relaxed, the spread of the disease will most likely revert back to its original exponential growth pattern. As such, the duration and severity of the lock-down measures should be carefully timed against their potentially devastating impact on the world economy., Comment: 9 pages, 3 figures, 2 tables, full article

Given $2k-1$ convex sets in $R^2$ such that no point of the plane is covered by more than $k$ of the sets, is it true that there are two among the convex sets whose union contains all $k$-covered points of the plane? This question due to Gy. Petruska has an obvious affirmative answer for $k=1,2,3$; we show here that the claim is also true for $k=4$, and we present a counterexample for $k=5$. We explain how Petruska's geometry question fits into the classical hypergraph extremal problems, called arrow problems, proposed by P. Erd\H{o}s., Comment: 13 pages

We studied, by scanning tunneling microscopy, the morphology of nanopits of monolayer depth created at graphite surfaces by hydrogen plasma etching under various conditions such as H$_2$ pressure, temperature, etching time, and RF power of the plasma generation. In addition to the known pressure-induced transition of the nanopit morphology, we found a sharp temperature-induced transition from many small rather round nanopits of ~150 nm size to few large hexagonal ones of 300-600 nm within a narrow temperature range. The remote and direct plasma modes switching mechanism, which was proposed to explain the pressure-induced transition, is not directly applicable to this newly found transition. Scanning tunneling spectroscopy (STS) measurements of edges of the hexagonal nanopits fabricated at graphite surfaces by this method show clear signatures of the peculiar electronic state localized at the zigzag edge (edge state), i.e., a prominent peak near the Fermi energy accompanied by suppressions on either side in the local density of states. These observations indicate that the hexagonal nanopits consist of a high density of zigzag edges. The STS data also revealed a domain structure of the edge state in which the electronic state varies over a length scale of ~3 nm along the edge. The present study will pave the way for microscopic understanding of the anisotropic etching mechanism and of spin polarization in zigzag nanoribbons which are promising key elements for future graphene nanoelectronics., Comment: 10 pages, 7 figures

Consider a $3$-uniform hypergraph of order $n$ with clique number $k$ such that the intersection of all its $k$-cliques is empty. Szemer\'edi and Petruska proved $n\leq 8m^2+3m$, for fixed $m=n-k$, and they conjectured the sharp bound $n\leq{m+2\choose 2}$. Tuza proved the best known bound, $n\leq \frac{3}{4}m^2+m+1$, using the machinery of $\tau$-critical hypergraphs. Here we propose an alternative approach, combining a decomposition process introduced by Szemer\'edi and Petruska with the skew version of Bollob\'as's theorem to prove $n\leq m^2 + 6m + 2$. While the bound obtained here is weaker than Tuza's bound, it is a proof-of-concept for a different approach and a call to apply dimension bounds from linear algebra., Comment: 9 pages, no figures: Version 2 reflects new information about the best known upper bound. We are very grateful to Zsolt Tuza for alerting us to the best known upper bound, $\frac{3}{4}m^2+m+1$, for the maximum order of a $\tau$-critical $3$-uniform hypergraph with transversal number $m$

Monolayer graphene epitaxially grown on SiC(0001) was etched by H-plasma and studied by scanning tunneling microscopy and spectroscopy. The etching created partly hexagonal nanopits of monatomic depth as well as elevated regions with a height of about 0.12 nm which are stable at $T$ = 78 K. The symmetric tunnel spectrum about the Femi energy and the absence of a $6\times6$ corrugation on the elevated regions suggest that in these regions the carbon buffer layer is decoupled from the SiC substrate and quasi-free-standing bilayer graphene appears at originally monolayer graphene on the buffer layer. This is a result of passivation of the SiC substrate by intercalated hydrogen as in previous reports for graphene on SiC(0001) heat treated in atomic hydrogen., Comment: 6 pages, 5 figures, ACSIN-14 and ICSPM-26 proceedings

A graph is an apex graph if it contains a vertex whose deletion leaves a planar graph. The family of apex graphs is minor-closed and so it is characterized by a finite list of minor-minimal non-members. The long-standing problem of determining this finite list of apex obstructions remains open. This paper determines the 133 minor-minimal, non-apex graphs that have connectivity two., Comment: 57 pages, 62 figures, 1 appendix Near final published version. Note that archive LaTeX processing creates g6 data contain apostrophe error ' should be `

Let $G$ be the Cartesian product of two finite paths, called a grid, and let $T$ be the set of eight distinct vertices of $G$, called terminals. Assume that $T$ is partitioned into four terminal pairs $\{s_i,t_i\}$, $1\leq i\leq 4$, to be linked in $G$ by using edge disjoint paths. To prove that such a linkage always exists we need a sequence of technical lemmas making possible for some terminals to `escape' from a $3\times 3$ corner of $Q\subset G$, called a `quadrant'. Here we state those lemmas, and give a proof for the cases when $Q$ contains at most $4$ terminals.

Let $Q$ be a finite subgraph of the integer grid $G$ in the plane, and let $T$ be a set of pairs of distinct vertices in $G$, called `terminal pairs'. Escaping a subset $X\subset T\cap Q$ from $Q$ means finding edge disjoint paths from the terminals in $X$ into distinct vertices of a set $L$ in the boundary of $Q$. Here we prove several lemmas for the cases where $Q$ is a $3\times 3$ grid, $L$ is the union of a vertical and horizontal boundary line of $Q$, furthermore, $T$ is a set of four terminal pairs in $G$ such that $|T\cap Q|\geq 5$. These lemmas are applied in [4] and complete the proof that the Cartesian product of two (one way) infinite paths has path-pairability number four.

Let $G=P_6\Box P_6$ be the $6\times 6$ grid, the Cartesian product of two paths of six vertices. Let $T$ be the set of eight distinct vertices of $G$, called terminals, and assume that $T$ is partitioned into four terminal pairs $\{s_i,t_i\}$, $1\leq i\leq 4$. We prove that $G$ is $4$-path-pairable, that is, for every $T$ there exist in $G$ pairwise edge disjoint $s_i,t_i$-paths, $1\leq i\leq 4$.